Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class J_DSU {
- 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) {
- return Integer.compare(this.time, other.time);
- }
- public void addFriend(Gamer gamer) {
- friends.add(gamer);
- }
- }
- class DSU {
- int n;
- int[] p;
- int[] size;
- DSU(int n) {
- this.n = n;
- p = new int[n];
- size = new int[n];
- for (int i = 0; i < n; i++) {
- p[i] = i;
- size[i] = 1;
- }
- }
- int getParent(int v) {
- if(p[v] == v) return v;
- return p[v] = getParent(p[v]);
- }
- void merge(int a, int b) {
- a = getParent(a);
- b = getParent(b);
- if(a == b) return;
- if(size[a] > size[b]) {
- p[b] = a;
- size[a] += size[b];
- } else {
- p[a] = b;
- size[b] += size[a];
- }
- }
- int getSize(int v) {
- v = getParent(v);
- return size[v];
- }
- }
- 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]);
- }
- Arrays.sort(gamers);
- DSU dsu = new DSU(n);
- long[] res = new long[p];
- int gamerPointer = n-1;
- boolean[] used = new boolean[n];
- for(int i = p-1; i >= 0; i--) {
- while (gamerPointer >= 0) {
- if(gamers[gamerPointer].time < max[i]) {
- break;
- }
- Gamer curGamer = gamers[gamerPointer];
- used[curGamer.index] = true;
- for(Gamer friend: curGamer.friends) {
- if(used[friend.index]) {
- dsu.merge(curGamer.index, friend.index);
- }
- }
- gamerPointer--;
- }
- int curSize = dsu.getSize(0);
- res[i] = curSize * 1l * g[i];
- }
- for(int i = 0; i < p; i++) {
- out.print(res[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_DSU().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