Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.StringTokenizer;
- import java.util.TreeSet;
- public class J_BFS {
- final boolean ONLINE_JUDGE = true;
- BufferedReader in;
- PrintWriter out;
- StringTokenizer tok = new StringTokenizer("");
- void solve() throws IOException {
- int t = 1;
- while (t-- > 0) {
- solveTest();
- }
- }
- class Gamer implements Comparable<Gamer> {
- int time;
- int index;
- List<Gamer> friends;
- public Gamer(int time, int index) {
- this.time = time;
- this.index = index;
- friends = new ArrayList<Gamer>();
- }
- public int compareTo(Gamer other) {
- int res = Integer.compare(this.time, other.time);
- if(res != 0) return res;
- return Integer.compare(this.index, other.index);
- }
- public void addFriend(Gamer gamer) {
- friends.add(gamer);
- }
- }
- private void solveTest() throws IOException {
- int n = readInt();
- int m = readInt();
- int p = readInt();
- Gamer[] gamers = new Gamer[n];
- gamers[0] = new Gamer(Integer.MAX_VALUE, 0);
- for (int i = 1; i < n; i++) {
- gamers[i] = new Gamer(readInt(), i);
- }
- int[] g = new int[p];
- int[] max = new int[p];
- for (int i = 0; i < p; i++) {
- g[i] = readInt();
- if (i == 0 || max[i - 1] < g[i]) {
- max[i] = g[i];
- } else {
- max[i] = max[i - 1];
- }
- }
- for (int i = 0; i < m; i++) {
- int from = readInt()-1;
- int to = readInt()-1;
- gamers[from].addFriend(gamers[to]);
- gamers[to].addFriend(gamers[from]);
- }
- TreeSet<Gamer> curSet = new TreeSet<Gamer>();
- curSet.add(gamers[0]);
- boolean[] used = new boolean[n];
- int[] end = new int[p];
- int usedCount = 0;
- for(int i = p-1; i >= 0; i--) {
- while(!curSet.isEmpty()) {
- Gamer maxGamer = curSet.last();
- if(maxGamer.time < max[i]) {
- break;
- }
- curSet.pollLast();
- usedCount++;
- end[i]++;
- used[maxGamer.index] = true;
- for(Gamer friend: maxGamer.friends) {
- if(!used[friend.index]) {
- curSet.add(friend);
- }
- }
- }
- }
- for(int i = 0; i < p; i++) {
- out.print(usedCount * 1l * g[i] + " ");
- usedCount -= end[i];
- }
- }
- void init() throws FileNotFoundException {
- if (ONLINE_JUDGE) {
- in = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- } else {
- in = new BufferedReader(new FileReader("input.txt"));
- out = new PrintWriter("output.txt");
- }
- }
- String readString() throws IOException {
- while (!tok.hasMoreTokens()) {
- tok = new StringTokenizer(in.readLine(), " .");
- }
- return tok.nextToken();
- }
- int readInt() throws IOException {
- return Integer.parseInt(readString());
- }
- long readLong() throws IOException {
- return Long.parseLong(readString());
- }
- double readDouble() throws IOException {
- return Double.parseDouble(readString());
- }
- int[] readArr(int n) throws IOException {
- int[] res = new int[n];
- for (int i = 0; i < n; i++) {
- res[i] = readInt();
- }
- return res;
- }
- long[] readArrL(int n) throws IOException {
- long[] res = new long[n];
- for (int i = 0; i < n; i++) {
- res[i] = readLong();
- }
- return res;
- }
- public static void main(String[] args) {
- new J_BFS().run();
- }
- public void run() {
- try {
- long t1 = System.currentTimeMillis();
- init();
- solve();
- out.close();
- long t2 = System.currentTimeMillis();
- System.err.println("Time = " + (t2 - t1));
- } catch (Exception e) {
- e.printStackTrace(System.err);
- System.exit(-1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement