oj.uz

답안 #129139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129139 2019-07-11T18:02:00 Z zeyad49 Designated Cities (JOI19_designated_cities) Java 11
0 / 100
 2000 ms 156008 KB 
import java.io.*;
import java.util.*;

public class designated_cities {
	static int n, timer, tin[], tout[], col[];
	static long down[], up[], maxDown[], maxNotInSub[];
	static ArrayList<Edge>[] adj;
	static ArrayList<Integer>[] subTrees;
	static long totalUp, totalDown;
	static TreeMap<Long, Integer> map;

	static class Edge {
		int v, cost1, cost2;

		Edge(int a, int b, int c) {
			v = a;
			cost1 = b;
			cost2 = c;
		}
	}

	static void dfs(int u, int p, int id) {
		tin[u] = timer++;
		maxDown[u] = down[u];
		col[u] = id;
		subTrees[id].add(u);
		int newId = id;
		for (Edge nxt : adj[u]) {
			int v = nxt.v;
			if (v == p)
				continue;
			up[v] = up[u] + nxt.cost2;
			totalUp += nxt.cost2;
			down[v] = down[u] + nxt.cost1;
			totalDown += nxt.cost1;
			dfs(v, u, p == -1 ? ++newId : newId);
			maxDown[u] = Math.max(maxDown[u], maxDown[v]);
		}
		tout[u] = timer - 1;
		map.put(down[u], map.getOrDefault(down[u], 0) + 1);

	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		n = sc.nextInt();
		adj = new ArrayList[n];
		tin = new int[n];
		tout = new int[n];
		down = new long[n];
		col = new int[n];
		up = new long[n];
		maxNotInSub = new long[n];
		maxDown = new long[n];
		map = new TreeMap<Long, Integer>();
		subTrees = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			adj[i] = new ArrayList();
			subTrees[i] = new ArrayList();
		}
		for (int i = 1; i < n; i++) {
			int u = sc.nextInt() - 1, v = sc.nextInt() - 1, c1 = sc.nextInt(), c2 = sc.nextInt();
			adj[u].add(new Edge(v, c1, c2));
			adj[v].add(new Edge(u, c2, c1));
		}
		dfs(0, -1, 0);
		long[] ans = new long[n + 1];
		for (int u = 0; u < n; u++) {
			ans[1] = Math.max(ans[1], totalUp - up[u] + down[u]);
		}
		for (int col = 1; col < n; col++) {
			for (int u : subTrees[col]) {
				map.put(down[u], map.get(down[u]) - 1);
				if (map.get(down[u]) == 0)
					map.remove(down[u]);
			}
			long max = map.lastKey();
			for (int u : subTrees[col]) {
				map.put(down[u], map.getOrDefault(down[u], 0) + 1);
				maxNotInSub[u] = max;
			}
		}
//		System.out.println(Arrays.toString(maxNotInSub));
		for (int u = 1; u < n; u++) {
			long curr = 0;
			// u and root
			curr = totalUp + down[u];
			ans[2] = Math.max(ans[2], curr);
			// u and some child for u
			curr = totalUp - up[u] + maxDown[u];
			ans[2] = Math.max(ans[2], curr);
			// u and some node v such that lca(v,u) = root
			curr = totalUp + down[u] + maxNotInSub[u];
			ans[2] = Math.max(ans[2], curr);

		}
		int q = sc.nextInt();
		while (q-- > 0) {
			out.println(totalUp + totalDown -ans[sc.nextInt()]);
		}
		out.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

}

Compilation message

Note: designated_cities.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 9944 KB Output is correct
2 Incorrect 91 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 9760 KB Output is correct
2 Execution timed out 2111 ms 155880 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 9820 KB Output is correct
2 Execution timed out 2129 ms 156008 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 9944 KB Output is correct
2 Incorrect 91 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 9760 KB Output is correct
2 Execution timed out 2111 ms 155880 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 9944 KB Output is correct
2 Incorrect 91 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -