Submission #8536322
Source Code Expand
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.IOException; import java.util.ArrayList; import java.io.UncheckedIOException; import java.util.List; import java.io.Closeable; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.InputStream; /** * Built using CHelper plug-in Actual solution is at the top */ public class Main { public static void main(String[] args) throws Exception { Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27); thread.start(); thread.join(); } static class TaskAdapter implements Runnable { @Override public void run() { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastInput in = new FastInput(inputStream); FastOutput out = new FastOutput(outputStream); TaskD solver = new TaskD(); solver.solve(1, in, out); out.close(); } } static class TaskD { public void solve(int testNumber, FastInput in, FastOutput out) { int n = in.readInt(); Node[] nodes = new Node[n + 1]; for (int i = 1; i <= n; i++) { nodes[i] = new Node(); nodes[i].id = i; } for (int i = 1; i < n; i++) { Edge e = new Edge(); e.a = nodes[in.readInt()]; e.b = nodes[in.readInt()]; e.length = in.readInt(); e.a.next.add(e); e.b.next.add(e); } dfs(nodes[1], null); List<Node> gs = new ArrayList<>(); findGravity(nodes[1], null, n, gs); long ans = 0; for (Node g : gs) { dfsForDepth(g, null, 0); long totalDepth = 0; long minDepth = (long) 1e18; for (int i = 1; i <= n; i++) { if (nodes[i].depth == 0) { continue; } totalDepth += nodes[i].depth; minDepth = Math.min(minDepth, nodes[i].depth); } for (Node node : gs) { if (g == node) { continue; } minDepth = node.depth; } ans = Math.max(ans, totalDepth * 2 - minDepth); } out.println(ans); } public void dfsForDepth(Node root, Edge p, long depth) { root.depth = depth; for (Edge e : root.next) { if (e == p) { continue; } Node node = e.other(root); dfsForDepth(node, e, depth + e.length); } } public void findGravity(Node root, Edge p, int total, List<Node> list) { int maxSize = 0; if (root.p != null) { maxSize = Math.max(maxSize, total - root.size); } for (Edge e : root.next) { if (e == p) { continue; } Node node = e.other(root); maxSize = Math.max(maxSize, node.size); } if (maxSize <= total / 2) { list.add(root); } for (Edge e : root.next) { if (e == p) { continue; } Node node = e.other(root); findGravity(node, e, total, list); } } public void dfs(Node root, Edge p) { if (p != null) { root.p = p.other(root); } root.size = 1; for (Edge e : root.next) { if (e == p) { continue; } Node node = e.other(root); dfs(node, e); root.size += node.size; } } } static class FastOutput implements AutoCloseable, Closeable { private StringBuilder cache = new StringBuilder(10 << 20); private final Writer os; public FastOutput(Writer os) { this.os = os; } public FastOutput(OutputStream os) { this(new OutputStreamWriter(os)); } public FastOutput println(long c) { cache.append(c).append('\n'); return this; } public FastOutput flush() { try { os.append(cache); os.flush(); cache.setLength(0); } catch (IOException e) { throw new UncheckedIOException(e); } return this; } public void close() { flush(); try { os.close(); } catch (IOException e) { throw new UncheckedIOException(e); } } public String toString() { return cache.toString(); } } static class FastInput { private final InputStream is; private byte[] buf = new byte[1 << 13]; private int bufLen; private int bufOffset; private int next; public FastInput(InputStream is) { this.is = is; } private int read() { while (bufLen == bufOffset) { bufOffset = 0; try { bufLen = is.read(buf); } catch (IOException e) { bufLen = -1; } if (bufLen == -1) { return -1; } } return buf[bufOffset++]; } public void skipBlank() { while (next >= 0 && next <= 32) { next = read(); } } public int readInt() { int sign = 1; skipBlank(); if (next == '+' || next == '-') { sign = next == '+' ? 1 : -1; next = read(); } int val = 0; if (sign == 1) { while (next >= '0' && next <= '9') { val = val * 10 + next - '0'; next = read(); } } else { while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } } return val; } } static class Edge { Node a; Node b; long length; public Node other(Node x) { return a == x ? b : a; } } static class Node { List<Edge> next = new ArrayList<>(); int size; Node p; long depth; int id; public String toString() { return "" + id; } } }
Submission Info
Submission Time | |
---|---|
Task | D - Tree and Hamilton Path |
User | daltao |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1100 |
Code Size | 7271 Byte |
Status | AC |
Exec Time | 686 ms |
Memory | 104484 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1100 / 1100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 78 ms | 42964 KB |
sample_02.txt | AC | 78 ms | 43092 KB |
subtask_1_01.txt | AC | 78 ms | 45908 KB |
subtask_1_02.txt | AC | 377 ms | 85024 KB |
subtask_1_03.txt | AC | 167 ms | 66036 KB |
subtask_1_04.txt | AC | 389 ms | 87148 KB |
subtask_1_05.txt | AC | 217 ms | 75364 KB |
subtask_1_06.txt | AC | 165 ms | 58168 KB |
subtask_1_07.txt | AC | 157 ms | 58256 KB |
subtask_1_08.txt | AC | 180 ms | 65252 KB |
subtask_1_09.txt | AC | 144 ms | 52308 KB |
subtask_1_10.txt | AC | 120 ms | 46060 KB |
subtask_1_11.txt | AC | 153 ms | 54324 KB |
subtask_1_12.txt | AC | 391 ms | 86960 KB |
subtask_1_13.txt | AC | 403 ms | 88112 KB |
subtask_1_14.txt | AC | 399 ms | 84520 KB |
subtask_1_15.txt | AC | 412 ms | 86880 KB |
subtask_1_16.txt | AC | 393 ms | 86436 KB |
subtask_1_17.txt | AC | 399 ms | 87080 KB |
subtask_1_18.txt | AC | 396 ms | 87028 KB |
subtask_1_19.txt | AC | 404 ms | 84564 KB |
subtask_1_20.txt | AC | 398 ms | 87028 KB |
subtask_1_21.txt | AC | 407 ms | 84468 KB |
subtask_1_22.txt | AC | 417 ms | 84596 KB |
subtask_1_23.txt | AC | 445 ms | 91636 KB |
subtask_1_24.txt | AC | 679 ms | 104484 KB |
subtask_1_25.txt | AC | 405 ms | 84596 KB |
subtask_1_26.txt | AC | 408 ms | 90356 KB |
subtask_1_27.txt | AC | 686 ms | 100804 KB |
subtask_1_28.txt | AC | 396 ms | 83828 KB |
subtask_1_29.txt | AC | 443 ms | 97620 KB |
subtask_1_30.txt | AC | 638 ms | 94888 KB |
subtask_1_31.txt | AC | 454 ms | 83120 KB |
subtask_1_32.txt | AC | 462 ms | 81344 KB |
subtask_1_33.txt | AC | 386 ms | 83936 KB |
subtask_1_34.txt | AC | 432 ms | 83420 KB |