Submission #1635981


Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Queue;

class Edge {
	int to;
	long weight;

	Edge(int to, long weight) {
		this.to = to;
		this.weight = weight;
	}
}

class Graph {
	int n;
	boolean directed;
	ArrayList<Node> ns;

	Graph(int n, boolean directed) {
		this.n = n;
		this.directed = directed;
		ns = new ArrayList<Node>();
		for (int i = 0; i < n; i++) {
			ns.add(new Node(i));
		}
	}

	void edge(int from, int to, long weight) {
		ns.get(from).edge(to, weight);
		if (!directed) {
			ns.get(to).edge(from, weight);
		}
	}

	void dfs(int from) {
		for (Node n : ns) {
			n.tmp = 0;
		}
		dfsImpl(from);
	}

	void dfsVisit(Node n) {
		// write code here...
	}

	private void dfsImpl(int from) {
		Node n = ns.get(from);
		if (n.tmp != 0)
			return;
		n.tmp = 1;
		dfsVisit(n);
		for (Edge e : n.es) {
			dfsImpl(e.to);
		}
	}

	void dijkstra1(int from) {
		for (int i = 0; i < n; i++) {
			ns.get(i).dist = Long.MAX_VALUE;
		}

		Queue<Node> q = new ArrayDeque<Node>();

		Node st = ns.get(from);
		st.dist = 0;
		q.add(st);

		while (!q.isEmpty()) {
			Node n = q.poll();
			long dist = n.dist;
			for (Edge e : n.es) {
				Node to = ns.get(e.to);
				if (to.dist > dist + 1) {
					to.dist = dist + 1;
					q.add(to);
				}
			}
		}
	}

	long diameter1() {
		dijkstra1(0);
		Node n1 = ns.get(0);

		for (int i = 1; i < n; i++) {
			if (ns.get(i).dist > n1.dist)
				n1 = ns.get(i);
		}

		dijkstra1(n1.idx);

		long diam = 0;
		for (int i = 0; i < n; i++) {
			if (ns.get(i).dist > diam)
				diam = ns.get(i).dist;
		}

		return diam;
	}
}

class Node {
	int idx;
	int tmp;
	ArrayList<Edge> es;

	long dist;

	Node(int idx) {
		this.idx = idx;
		es = new ArrayList<Edge>();
	}

	void edge(int to, long weight) {
		es.add(new Edge(to, weight));
	}
}

public class Main {
	private static void solve() {
		int n1 = nei();
		int m1 = nei();
		int[][] es1 = nis2(m1, 2);
		Graph g1 = new Graph(n1, false);
		for (int i = 0; i < m1; i++) {
			g1.edge(es1[i][0], es1[i][1], 1);
		}

		int n2 = nei();
		int m2 = nei();
		int[][] es2 = nis2(m2, 2);
		Graph g2 = new Graph(n2, false);
		for (int i = 0; i < m2; i++) {
			g2.edge(es2[i][0], es2[i][1], 1);
		}
		long d1 = g1.diameter1();
		long d2 = g2.diameter1();

		out(max(max(d1, d2), ((d1 + 1 >> 1) + 1 + (d2 + 1 >> 1))) + " " + (d1 + d2 + 1));
	}

	static int[] lis(int[] s) {
		int n = s.length;
		int[] dp = new int[n];
		int[] ids = new int[n];
		int[] pids = new int[n];
		dp[0] = s[0];
		int len = 1;
		int lidx = 0;
		for (int i = 1; i < n; i++) {
			int idx = bs(s[i], dp, 0, len);
			dp[idx] = s[i];
			ids[idx] = i;
			if (idx == len) {
				lidx = i;
				len++;
			}
			if (idx > 0)
				pids[i] = ids[idx - 1];
		}
		int[] lis = new int[len];
		lis[len - 1] = s[lidx];
		for (int i = len - 1; i >= 0; i--) {
			lis[i] = s[lidx];
			lidx = pids[lidx];
		}
		return lis;
	}

	static int bs(int a, int[] as, int from, int num) {
		int min = from;
		int max = from + num - 1;
		while (min < max) {
			int mid = min + max >> 1;
			if (as[mid] < a)
				min = mid + 1;
			else if (as[mid] > a)
				max = mid;
			else
				return mid;
		}
		return as[min] < a ? min + 1 : min;
	}

	static int gcd(int x, int y) {
		x = (x ^ x >> 31) - (x >> 31);
		y = (y ^ y >> 31) - (y >> 31);
		if (x < y) {
			x ^= y;
			y ^= x;
			x ^= y;
		}
		int z = x % y;
		if (z == 0)
			return y;
		return gcd(y, z);
	}

	static long gcd(long x, long y) {
		x = (x ^ x >> 63) - (x >> 63);
		y = (y ^ y >> 63) - (y >> 63);
		if (x < y) {
			x ^= y;
			y ^= x;
			x ^= y;
		}
		long z = x % y;
		if (z == 0)
			return y;
		return gcd(y, z);
	}

	static int lcm(int x, int y) {
		x = (x ^ x >> 31) - (x >> 31);
		y = (y ^ y >> 31) - (y >> 31);
		return x / gcd(x, y) * y;
	}

	static long lcm(long x, long y) {
		x = (x ^ x >> 63) - (x >> 63);
		y = (y ^ y >> 63) - (y >> 63);
		return x / gcd(x, y) * y;
	}

	static int abs(int x) {
		return x < 0 ? -x : x;
	}

	static long abs(long x) {
		return x < 0 ? -x : x;
	}

	static int min(int a, int b) {
		return a < b ? a : b;
	}

	static long min(long a, long b) {
		return a < b ? a : b;
	}

	static int max(int a, int b) {
		return a > b ? a : b;
	}

	static long max(long a, long b) {
		return a > b ? a : b;
	}

	static int clamp(int a, int min, int max) {
		return a < min ? min : a > max ? max : a;
	}

	static long clamp(long a, long min, long max) {
		return a < min ? min : a > max ? max : a;
	}

	static void out(String val) {
		IO.out(val);
	}

	static void out(Object val) {
		IO.out(String.valueOf(val));
	}

	static void out(int val) {
		IO.out(String.valueOf(val));
	}

	static void out(long val) {
		IO.out(String.valueOf(val));
	}

	static void out(char val) {
		IO.out(String.valueOf(val));
	}

	static void out(float val) {
		IO.out(String.valueOf(val));
	}

	static void out(double val) {
		IO.out(String.valueOf(val));
	}

	static void out(boolean val) {
		IO.out(String.valueOf(val));
	}

	static void kil(String val) {
		IO.out(val);
		IO.flush();
		System.exit(0);
	}

	static void kil(Object val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(int val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(long val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(char val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(float val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(double val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static void kil(boolean val) {
		IO.out(String.valueOf(val));
		IO.flush();
		System.exit(0);
	}

	static String nes() {
		return IO.next();
	}

	static int nei() {
		return IO.nextInt();
	}

	static long nel() {
		return IO.nextLong();
	}

	static String[] nss(int n) {
		String[] as = new String[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.next();
		}
		return as;
	}

	static int[] nis(int n) {
		int[] as = new int[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.nextInt();
		}
		return as;
	}

	static long[] nls(int n) {
		long[] as = new long[n];
		for (int i = 0; i < n; i++) {
			as[i] = IO.nextLong();
		}
		return as;
	}

	static String[][] nss2(int n, int m) {
		String[][] as = new String[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.next();
			}
		}
		return as;
	}

	static int[][] nis2(int n, int m) {
		int[][] as = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.nextInt();
			}
		}
		return as;
	}

	static long[][] nls2(int n, int m) {
		long[][] as = new long[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				as[i][j] = IO.nextLong();
			}
		}
		return as;
	}

	static int parseInt(String val) {
		return Integer.parseInt(val);
	}

	static int parseInt(char val) {
		return Integer.parseInt(String.valueOf(val));
	}

	static long parseLong(String val) {
		return Long.parseLong(val);
	}

	public static void main(String[] args) {
		try {
			solve();
			IO.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

final class IO {
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out, false);
	private static final byte[] buffer = new byte[1024];
	private static int ptr = 0;
	private static int len = 0;

	private static boolean hasNextByte() {
		if (ptr < len)
			return true;
		ptr = 0;
		try {
			len = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		return len > 0;
	}

	private static int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	static boolean hasNext() {
		byte c;
		while (hasNextByte() && ((c = buffer[ptr]) < '!' || c > '~'))
			ptr++;
		return hasNextByte();
	}

	static String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (b >= '!' && b <= '~') {
			sb.append((char) b);
			b = readByte();
		}
		return sb.toString();
	}

	static long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		int sign = 1;
		int b = readByte();
		if (b == '-') {
			sign = -1;
			b = readByte();
		}
		if (b < '0' || '9' < b)
			throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9')
				n = n * 10 + b - '0';
			else if (b == -1 || b < '!' || b > '~')
				return n * sign;
			else
				throw new NumberFormatException();
			b = readByte();
		}
	}

	static int nextInt() {
		if (!hasNext())
			throw new NoSuchElementException();
		int n = 0;
		int sign = 1;
		int b = readByte();
		if (b == '-') {
			sign = -1;
			b = readByte();
		}
		if (b < '0' || '9' < b)
			throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9')
				n = n * 10 + b - '0';
			else if (b == -1 || b < '!' || b > '~')
				return n * sign;
			else
				throw new NumberFormatException();
			b = readByte();
		}
	}

	static void out(String val) {
		out.println(val);
	}

	static void flush() {
		out.flush();
	}
}

Submission Info

Submission Time
Task C - 直径
User saharan
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 9786 Byte
Status WA
Exec Time 115 ms
Memory 25044 KB

Judge Result

Set Name Small Large
Score / Max Score 0 / 50 0 / 50
Status
AC × 21
WA × 7
AC × 46
WA × 12
Set Name Test Cases
Small 10-small_random-00, 10-small_random-01, 10-small_random-02, 10-small_random-03, 10-small_random-04, 10-small_random-05, 10-small_random-06, 10-small_random-07, 10-small_random-08, 10-small_random-09, 10-small_random-10, 10-small_random-11, 10-small_random-12, 10-small_random-13, 10-small_random-14, 10-small_random-15, 10-small_random-16, 10-small_random-17, 10-small_random-18, 10-small_random-19, 21-small_path-00, 21-small_path-01, 21-small_path-02, 21-small_path-03, 21-small_path-04, 00-sample-00, 00-sample-01, 00-sample-02
Large 00-sample-00, 00-sample-01, 00-sample-02, 10-small_random-00, 10-small_random-01, 10-small_random-02, 10-small_random-03, 10-small_random-04, 10-small_random-05, 10-small_random-06, 10-small_random-07, 10-small_random-08, 10-small_random-09, 10-small_random-10, 10-small_random-11, 10-small_random-12, 10-small_random-13, 10-small_random-14, 10-small_random-15, 10-small_random-16, 10-small_random-17, 10-small_random-18, 10-small_random-19, 20-small_tree-00, 20-small_tree-01, 20-small_tree-02, 20-small_tree-03, 20-small_tree-04, 21-small_path-00, 21-small_path-01, 21-small_path-02, 21-small_path-03, 21-small_path-04, 30-large_random-00, 30-large_random-01, 30-large_random-02, 30-large_random-03, 30-large_random-04, 30-large_random-05, 30-large_random-06, 30-large_random-07, 30-large_random-08, 30-large_random-09, 40-large_comp-00, 40-large_comp-01, 40-large_comp-02, 40-large_comp-03, 40-large_comp-04, 41-large_tree-00, 41-large_tree-01, 41-large_tree-02, 41-large_tree-03, 41-large_tree-04, 42-large_path-00, 42-large_path-01, 42-large_path-02, 42-large_path-03, 42-large_path-04
Case Name Status Exec Time Memory
00-sample-00 AC 76 ms 21332 KB
00-sample-01 AC 73 ms 21076 KB
00-sample-02 AC 71 ms 19028 KB
10-small_random-00 AC 73 ms 21460 KB
10-small_random-01 AC 80 ms 20564 KB
10-small_random-02 AC 73 ms 19796 KB
10-small_random-03 AC 74 ms 21460 KB
10-small_random-04 WA 75 ms 21716 KB
10-small_random-05 AC 74 ms 18772 KB
10-small_random-06 AC 72 ms 17108 KB
10-small_random-07 WA 72 ms 21460 KB
10-small_random-08 AC 72 ms 21332 KB
10-small_random-09 AC 73 ms 18004 KB
10-small_random-10 AC 75 ms 21332 KB
10-small_random-11 AC 74 ms 21076 KB
10-small_random-12 AC 82 ms 21332 KB
10-small_random-13 AC 72 ms 19412 KB
10-small_random-14 WA 79 ms 21076 KB
10-small_random-15 WA 73 ms 20692 KB
10-small_random-16 AC 74 ms 19796 KB
10-small_random-17 WA 76 ms 19028 KB
10-small_random-18 WA 89 ms 25044 KB
10-small_random-19 WA 85 ms 19796 KB
20-small_tree-00 AC 76 ms 19028 KB
20-small_tree-01 AC 72 ms 21460 KB
20-small_tree-02 AC 77 ms 19284 KB
20-small_tree-03 AC 71 ms 21460 KB
20-small_tree-04 AC 87 ms 21460 KB
21-small_path-00 AC 71 ms 20052 KB
21-small_path-01 AC 75 ms 19412 KB
21-small_path-02 AC 76 ms 20436 KB
21-small_path-03 AC 73 ms 19668 KB
21-small_path-04 AC 73 ms 18516 KB
30-large_random-00 WA 109 ms 19924 KB
30-large_random-01 AC 77 ms 21204 KB
30-large_random-02 AC 92 ms 20180 KB
30-large_random-03 AC 73 ms 20180 KB
30-large_random-04 WA 94 ms 19924 KB
30-large_random-05 AC 72 ms 21332 KB
30-large_random-06 WA 82 ms 21588 KB
30-large_random-07 AC 85 ms 23124 KB
30-large_random-08 WA 113 ms 22356 KB
30-large_random-09 WA 115 ms 22228 KB
40-large_comp-00 AC 74 ms 19284 KB
40-large_comp-01 AC 79 ms 18516 KB
40-large_comp-02 AC 75 ms 20692 KB
40-large_comp-03 AC 98 ms 21972 KB
40-large_comp-04 AC 107 ms 22564 KB
41-large_tree-00 AC 79 ms 21204 KB
41-large_tree-01 AC 79 ms 21460 KB
41-large_tree-02 AC 78 ms 21204 KB
41-large_tree-03 AC 80 ms 20436 KB
41-large_tree-04 AC 91 ms 22996 KB
42-large_path-00 AC 85 ms 19412 KB
42-large_path-01 AC 73 ms 21332 KB
42-large_path-02 AC 77 ms 21332 KB
42-large_path-03 AC 84 ms 20436 KB
42-large_path-04 AC 87 ms 23636 KB