Advertisement
Guest User

J - A lot of time (BFS)

a guest
Jun 23rd, 2015
409
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.42 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. import java.util.StringTokenizer;
  5. import java.util.TreeSet;
  6.  
  7. public class J_BFS {
  8.  
  9.     final boolean ONLINE_JUDGE = true;
  10.     BufferedReader in;
  11.     PrintWriter out;
  12.     StringTokenizer tok = new StringTokenizer("");
  13.  
  14.     void solve() throws IOException {
  15.         int t = 1;
  16.         while (t-- > 0) {
  17.             solveTest();
  18.         }
  19.     }
  20.  
  21.  
  22.     class Gamer implements Comparable<Gamer> {
  23.         int time;
  24.         int index;
  25.         List<Gamer> friends;
  26.  
  27.         public Gamer(int time, int index) {
  28.             this.time = time;
  29.             this.index = index;
  30.             friends = new ArrayList<Gamer>();
  31.         }
  32.  
  33.         public int compareTo(Gamer other) {
  34.             int res = Integer.compare(this.time, other.time);
  35.             if(res != 0) return res;
  36.             return Integer.compare(this.index, other.index);
  37.         }
  38.  
  39.         public void addFriend(Gamer gamer) {
  40.             friends.add(gamer);
  41.         }
  42.     }
  43.  
  44.     private void solveTest() throws IOException {
  45.         int n = readInt();
  46.         int m = readInt();
  47.         int p = readInt();
  48.         Gamer[] gamers = new Gamer[n];
  49.         gamers[0] = new Gamer(Integer.MAX_VALUE, 0);
  50.         for (int i = 1; i < n; i++) {
  51.             gamers[i] = new Gamer(readInt(), i);
  52.         }
  53.         int[] g = new int[p];
  54.         int[] max = new int[p];
  55.         for (int i = 0; i < p; i++) {
  56.             g[i] = readInt();
  57.             if (i == 0 || max[i - 1] < g[i]) {
  58.                 max[i] = g[i];
  59.             } else {
  60.                 max[i] = max[i - 1];
  61.             }
  62.         }
  63.         for (int i = 0; i < m; i++) {
  64.             int from = readInt()-1;
  65.             int to = readInt()-1;
  66.             gamers[from].addFriend(gamers[to]);
  67.             gamers[to].addFriend(gamers[from]);
  68.         }
  69.  
  70.         TreeSet<Gamer> curSet = new TreeSet<Gamer>();
  71.         curSet.add(gamers[0]);
  72.         boolean[] used = new boolean[n];
  73.         int[] end = new int[p];
  74.         int usedCount = 0;
  75.         for(int i = p-1; i >= 0; i--) {
  76.             while(!curSet.isEmpty()) {
  77.                 Gamer maxGamer = curSet.last();
  78.                 if(maxGamer.time < max[i]) {
  79.                     break;
  80.                 }
  81.  
  82.                 curSet.pollLast();
  83.                 usedCount++;
  84.                 end[i]++;
  85.                 used[maxGamer.index] = true;
  86.                 for(Gamer friend: maxGamer.friends) {
  87.                     if(!used[friend.index]) {
  88.                         curSet.add(friend);
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.         for(int i = 0; i < p; i++) {
  94.             out.print(usedCount * 1l * g[i] + " ");
  95.             usedCount -= end[i];
  96.         }
  97.     }
  98.  
  99.     void init() throws FileNotFoundException {
  100.         if (ONLINE_JUDGE) {
  101.             in = new BufferedReader(new InputStreamReader(System.in));
  102.             out = new PrintWriter(System.out);
  103.         } else {
  104.             in = new BufferedReader(new FileReader("input.txt"));
  105.             out = new PrintWriter("output.txt");
  106.         }
  107.     }
  108.  
  109.     String readString() throws IOException {
  110.         while (!tok.hasMoreTokens()) {
  111.             tok = new StringTokenizer(in.readLine(), " .");
  112.         }
  113.         return tok.nextToken();
  114.     }
  115.  
  116.     int readInt() throws IOException {
  117.         return Integer.parseInt(readString());
  118.     }
  119.  
  120.     long readLong() throws IOException {
  121.         return Long.parseLong(readString());
  122.     }
  123.  
  124.     double readDouble() throws IOException {
  125.         return Double.parseDouble(readString());
  126.     }
  127.  
  128.     int[] readArr(int n) throws IOException {
  129.         int[] res = new int[n];
  130.         for (int i = 0; i < n; i++) {
  131.             res[i] = readInt();
  132.         }
  133.         return res;
  134.     }
  135.  
  136.     long[] readArrL(int n) throws IOException {
  137.         long[] res = new long[n];
  138.         for (int i = 0; i < n; i++) {
  139.             res[i] = readLong();
  140.         }
  141.         return res;
  142.     }
  143.  
  144.     public static void main(String[] args) {
  145.         new J_BFS().run();
  146.     }
  147.  
  148.     public void run() {
  149.         try {
  150.             long t1 = System.currentTimeMillis();
  151.             init();
  152.             solve();
  153.             out.close();
  154.             long t2 = System.currentTimeMillis();
  155.             System.err.println("Time = " + (t2 - t1));
  156.         } catch (Exception e) {
  157.             e.printStackTrace(System.err);
  158.             System.exit(-1);
  159.         }
  160.     }
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement