oj.uz

답안 #129142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129142 2019-07-11T18:06:46 Z zeyad49 Designated Cities (JOI19_designated_cities) Java 11
0 / 100
 2000 ms 149828 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 col = 1; col < n; col++) {
			for (int u : subTrees[col]) {
				int k= map.get(down[u]);
				map.put(down[u], k- 1);
				if (k == 1)
					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 = 0; u < n; u++) {
			ans[1] = Math.max(ans[1], totalUp - up[u] + down[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 =Math.max(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 = Math.max(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 86 ms 9844 KB Output is correct
2 Incorrect 90 ms 9752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 9908 KB Output is correct
2 Execution timed out 2123 ms 139836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 9844 KB Output is correct
2 Execution timed out 2078 ms 149828 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 9844 KB Output is correct
2 Incorrect 90 ms 9752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 9908 KB Output is correct
2 Execution timed out 2123 ms 139836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 9844 KB Output is correct
2 Incorrect 90 ms 9752 KB Output isn't correct
3 Halted 0 ms 0 KB -