Submission #2226194


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			int k = in.nextInt();
			int l = in.nextInt();
			UnionFind u1 = new UnionFind(n);
			UnionFind u2 = new UnionFind(n);
			for (int i = 0; i < k; i++) {
				int p = in.nextInt()-1;
				int q = in.nextInt()-1;
				u1.link(p, q);
			}
			for (int i = 0; i < l; i++) {
				int r = in.nextInt()-1;
				int s = in.nextInt()-1;
				u2.link(r, s);
			}
			Map<Long, Integer> roots = new HashMap<Long, Integer>();
			for (int i = 0; i < n; i++) {
				long code = (long)u1.root(i)<< 32 | u2.root(i);
				roots.merge(code, 1, Integer::sum);
			}
			for (int i = 0; i < n; i++) {
				if (i > 0)out.print(" ");
				long code = (long)u1.root(i) << 32 | u2.root(i);
				out.print(roots.get(code));
			}

		}

		public class UnionFind {
			int[] data;

			public UnionFind(int n) {
				data = new int[n];
				Arrays.fill(data, -1);
			}

			boolean link(int x, int y) {
				x = root(x);
				y = root(y);
				if (x != y) {
					if (data[y] < data[x]) {
						data[y] += data[x];
						data[x] = y;
					} else {
						data[x] += data[y];
						data[y] = x;
					}
				}
				return x != y;
			}

			int root(int x) {
				return data[x] < 0 ? x : (data[x] = root(data[x]));
			}
		}
	}


	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}

Submission Info

Submission Time
Task D - Connectivity
User tutuz
Language Java8 (OpenJDK 1.8.0)
Score 400
Code Size 3004 Byte
Status AC
Exec Time 695 ms
Memory 80036 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 18
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt AC 185 ms 24660 KB
subtask0_1.txt AC 153 ms 23892 KB
subtask0_2.txt AC 149 ms 24532 KB
subtask1_0.txt AC 346 ms 43452 KB
subtask1_1.txt AC 695 ms 80036 KB
subtask1_10.txt AC 368 ms 44352 KB
subtask1_11.txt AC 650 ms 69448 KB
subtask1_12.txt AC 606 ms 70368 KB
subtask1_13.txt AC 595 ms 70368 KB
subtask1_14.txt AC 665 ms 64136 KB
subtask1_2.txt AC 549 ms 54664 KB
subtask1_3.txt AC 622 ms 70948 KB
subtask1_4.txt AC 635 ms 66368 KB
subtask1_5.txt AC 372 ms 45152 KB
subtask1_6.txt AC 626 ms 70780 KB
subtask1_7.txt AC 620 ms 72996 KB
subtask1_8.txt AC 640 ms 71620 KB
subtask1_9.txt AC 609 ms 54800 KB