Submission #3063358
Source Code Expand
// package other2015.utpc2014; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; public class Main { static long __startTime = System.currentTimeMillis(); static Vertex[] graph; static void dfs(Vertex v, Vertex p) { v.count = 1; v.parent = p == null ? -1 : p.idx; for (Edge e : v.adj) { int to = e.u + e.v - v.idx; if (p != null && to == p.idx) { continue; } dfs(graph[to], v); v.count += graph[to].count; } } static List<Edge> tmpedges; static void dfsFrom(Vertex v, Vertex p) { for (Edge e : v.adj) { int to = e.u + e.v - v.idx; if (p != null && to == p.idx) { continue; } tmpedges.add(e); dfsFrom(graph[to], v); } } static class Group { TreeSet<Edge> edges; int root; public Group(List<Edge> e, int r) { edges = new TreeSet<>(e); root = r; dfs(graph[root], null); } public void operate(int e, int s, int d) { Edge ed = edges.ceiling(new Edge(e, -1, -1, s)); edges.remove(ed); ed.strength += d; edges.add(ed); } public int[] cutmin() { Edge min = edges.first(); edges.remove(min); Vertex newRoot = graph[min.u].parent == min.v ? graph[min.u] : graph[min.v]; Vertex newRootParent = graph[newRoot.parent]; newRoot.adj.remove(min); newRootParent.adj.remove(min); tmpedges = new ArrayList<>(); if (graph[root].count < newRoot.count * 2) { dfsFrom(graph[root], null); for (Edge e : tmpedges) { edges.remove(e); } int newSmallRoot = root; root = newRoot.idx; return new int[]{newSmallRoot, min.idx}; } else { dfsFrom(newRoot, null); for (Edge e : tmpedges) { edges.remove(e); } return new int[]{newRoot.idx, min.idx}; } } } static class Vertex { TreeSet<Edge> adj; int idx; int parent; int count; public Vertex(int id) { idx = id; adj = new TreeSet<>(); parent = -1; count = 0; } } static class Edge implements Comparable<Edge> { int idx; int u; int v; int strength; public Edge(int i, int a, int b, int c) { idx = i; u = a; v = b; strength = c; } @Override public int compareTo(Edge o) { return strength == o.strength ? idx - o.idx : strength - o.strength; } } public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.nextInt(); int[] edgeId = new int[n-1]; int[] str = new int[n-1]; List<Edge> edges = new ArrayList<>(); List<Group> g = new ArrayList<>(); for (int i = 0; i < n-1; i++) { Edge e = new Edge(i, in.nextInt()-1, in.nextInt()-1, in.nextInt()); edges.add(e); str[i] = e.strength; } graph = new Vertex[n]; for (int i = 0; i < n ; i++) { graph[i] = new Vertex(i); } for (Edge e : edges) { graph[e.u].adj.add(e); graph[e.v].adj.add(e); } g.add(new Group(edges, 0)); int q = in.nextInt(); while (--q >= 0) { int type = in.nextInt(); int e = in.nextInt()-1; int gid = edgeId[e]; if (type == 1) { int d = in.nextInt(); if (gid == -1) { continue; } g.get(gid).operate(e, str[e], d); str[e] += d; } else { if (gid == -1) { out.println(-1); } else { int[] pair = g.get(gid).cutmin(); edgeId[pair[1]] = -1; int ngid = g.size(); for (Edge ed : tmpedges) { edgeId[ed.idx] = ngid; } g.add(new Group(tmpedges, pair[0])); out.println(pair[1]+1); } } } out.flush(); } private static void printTime(String label) { debug(label, System.currentTimeMillis() - __startTime); } public static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } public static class InputReader { private static final int BUFFER_LENGTH = 1 << 12; private InputStream stream; private byte[] buf = new byte[BUFFER_LENGTH]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { return (char) skipWhileSpace(); } public String nextToken() { int c = skipWhileSpace(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { int c = skipWhileSpace(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public double nextDouble() { return Double.valueOf(nextToken()); } int skipWhileSpace() { int c = next(); while (isSpaceChar(c)) { c = next(); } return c; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | I - 盆栽 |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 7445 Byte |
Status | WA |
Exec Time | 5262 ms |
Memory | 159004 KB |
Judge Result
Set Name | Subtask | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 30 | 0 / 270 | ||||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask | atetubou-challenge1.in, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt |
All | scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
scrambled_00.txt | AC | 76 ms | 18644 KB |
scrambled_01.txt | WA | 111 ms | 23508 KB |
scrambled_02.txt | AC | 116 ms | 22868 KB |
scrambled_03.txt | AC | 117 ms | 20948 KB |
scrambled_04.txt | AC | 108 ms | 21716 KB |
scrambled_05.txt | AC | 112 ms | 21460 KB |
scrambled_06.txt | AC | 112 ms | 21076 KB |
scrambled_07.txt | WA | 119 ms | 20692 KB |
scrambled_08.txt | WA | 119 ms | 21844 KB |
scrambled_09.txt | AC | 116 ms | 22100 KB |
scrambled_10.txt | WA | 108 ms | 21204 KB |
scrambled_11.txt | TLE | 5258 ms | 156300 KB |
scrambled_12.txt | TLE | 5262 ms | 154444 KB |
scrambled_13.txt | WA | 2556 ms | 140496 KB |
scrambled_14.txt | TLE | 5262 ms | 147272 KB |
scrambled_15.txt | TLE | 5262 ms | 153272 KB |
scrambled_16.txt | TLE | 5262 ms | 159004 KB |
scrambled_17.txt | WA | 3556 ms | 156428 KB |
scrambled_18.txt | TLE | 5262 ms | 148252 KB |
scrambled_19.txt | TLE | 5258 ms | 153488 KB |
scrambled_20.txt | TLE | 5262 ms | 150056 KB |
scrambled_21.txt | AC | 990 ms | 103364 KB |
scrambled_22.txt | AC | 124 ms | 21224 KB |
scrambled_23.txt | AC | 119 ms | 22632 KB |
scrambled_24.txt | AC | 115 ms | 23152 KB |
scrambled_25.txt | AC | 121 ms | 22500 KB |
scrambled_26.txt | AC | 130 ms | 21044 KB |
scrambled_27.txt | AC | 1144 ms | 110552 KB |
scrambled_28.txt | AC | 1311 ms | 112584 KB |
scrambled_29.txt | AC | 1107 ms | 98660 KB |
scrambled_30.txt | AC | 1156 ms | 104468 KB |
scrambled_31.txt | AC | 1394 ms | 110316 KB |
scrambled_32.txt | AC | 71 ms | 19028 KB |
subtask_00.txt | AC | 71 ms | 20180 KB |
subtask_01.txt | WA | 125 ms | 23380 KB |
subtask_02.txt | AC | 111 ms | 20308 KB |
subtask_03.txt | AC | 111 ms | 19924 KB |
subtask_04.txt | AC | 113 ms | 23636 KB |
subtask_05.txt | AC | 111 ms | 19152 KB |
subtask_06.txt | AC | 111 ms | 20564 KB |
subtask_07.txt | WA | 110 ms | 19796 KB |
subtask_08.txt | WA | 122 ms | 20180 KB |
subtask_09.txt | AC | 115 ms | 19284 KB |
subtask_10.txt | WA | 124 ms | 23508 KB |
subtask_11.txt | AC | 121 ms | 24516 KB |
subtask_12.txt | AC | 120 ms | 22524 KB |
subtask_13.txt | AC | 125 ms | 21044 KB |
subtask_14.txt | AC | 125 ms | 20788 KB |
subtask_15.txt | AC | 123 ms | 26164 KB |
subtask_16.txt | AC | 70 ms | 21588 KB |