Submission #3065234
Source Code Expand
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; public class Main { private static void solve() { int n = ni(); int[] from = new int[n - 1]; int[] to = new int[n - 1]; int[] w = new int[n - 1]; int[] idx = new int[n - 1]; for (int i = 0; i < n - 1; i ++) { from[i] = ni() - 1; to[i] = ni() - 1; w[i] = ni(); idx[i] = i; } int[][][] g = packWU(n, from, to, idx); Comparator<Integer> cmp = (o1, o2) -> w[o1] == w[o2] ? o1 - o2 : w[o1] - w[o2]; List<PriorityQueue<Integer>> qlist = new ArrayList<>();; PriorityQueue<Integer> sq = new PriorityQueue<>(cmp); int[] edgeSet = new int[n - 1]; for (int i = 0; i < n - 1; i ++) { sq.add(i); } qlist.add(sq); int[] left = new int[n]; int[] right = new int[n]; int q = ni(); for (int i = 0; i < q; i ++) { int type = ni(); if (type == 1) { int e = ni() - 1; int d = ni(); qlist.get(edgeSet[e]).remove(e); w[e] = d; qlist.get(edgeSet[e]).add(e); } else { int e = ni() - 1; if (w[e] == Integer.MIN_VALUE) { out.println(-1); continue; } int v = qlist.get(edgeSet[e]).poll(); out.println(v + 1); w[v] = Integer.MIN_VALUE; int lc = dfs(from[v], to[v], g, w, left); int rc = dfs(to[v], from[v], g, w, right); int[] next = lc < rc ? left : right; int cnt = Math.min(lc, rc); PriorityQueue<Integer> nq = new PriorityQueue<>(cmp); PriorityQueue<Integer> cq = qlist.get(edgeSet[v]); int ni = qlist.size(); for (int j = 0; j < cnt; j ++) { nq.add(next[j]); cq.remove(next[j]); edgeSet[next[j]] = ni; } qlist.add(nq); } } } private static int dfs(int now, int pre, int[][][] g, int[] w, int[] ret) { ArrayDeque<int[]> q = new ArrayDeque<>(); q.add(new int[] {now, pre}); int ptr = 0; while (q.size() > 0) { int[] e = q.poll(); now = e[0]; pre = e[1]; for (int[] f : g[now]) { if (f[0] == pre || w[f[1]] == Integer.MIN_VALUE) continue; q.add(new int[] {f[0], now}); ret[ptr ++] = f[1]; } } return ptr; } public static int[][][] packWU(int n, int[] from, int[] to, int[] w){ return packWU(n, from, to, w, from.length); } public static int[][][] packWU(int n, int[] from, int[] to, int[] w, int sup) { int[][][] g = new int[n][][]; int[] p = new int[n]; for(int i = 0;i < sup;i++)p[from[i]]++; for(int i = 0;i < sup;i++)p[to[i]]++; for(int i = 0;i < n;i++)g[i] = new int[p[i]][2]; for(int i = 0;i < sup;i++){ --p[from[i]]; g[from[i]][p[from[i]]][0] = to[i]; g[from[i]][p[from[i]]][1] = w[i]; --p[to[i]]; g[to[i]][p[to[i]]][0] = from[i]; g[to[i]][p[to[i]]][1] = w[i]; } return g; } public static void main(String[] args) { new Thread(null, new Runnable() { @Override public void run() { long start = System.currentTimeMillis(); String debug = System.getProperty("debug"); if (debug != null) { try { is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug)); } catch (Exception e) { throw new RuntimeException(e); } } reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768); solve(); out.flush(); tr((System.currentTimeMillis() - start) + "ms"); } }, "", 64000000).start(); } private static java.io.InputStream is = System.in; private static java.io.PrintWriter out = new java.io.PrintWriter(System.out); private static java.util.StringTokenizer tokenizer = null; private static java.io.BufferedReader reader; public static String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new java.util.StringTokenizer(reader.readLine()); } catch (Exception e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } private static double nd() { return Double.parseDouble(next()); } private static long nl() { return Long.parseLong(next()); } private static int[] na(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = ni(); return a; } private static char[] ns() { return next().toCharArray(); } private static long[] nal(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nl(); return a; } private static int[][] ntable(int n, int m) { int[][] table = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j] = ni(); } } return table; } private static int[][] nlist(int n, int m) { int[][] table = new int[m][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[j][i] = ni(); } } return table; } private static int ni() { return Integer.parseInt(next()); } private static void tr(Object... o) { if (is != System.in) System.out.println(java.util.Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | I - 盆栽 |
User | hiromi_ayase |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 5642 Byte |
Status | WA |
Exec Time | 5267 ms |
Memory | 374764 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 | 180 ms | 26964 KB |
scrambled_01.txt | WA | 206 ms | 29012 KB |
scrambled_02.txt | WA | 196 ms | 30804 KB |
scrambled_03.txt | WA | 212 ms | 26452 KB |
scrambled_04.txt | WA | 203 ms | 28884 KB |
scrambled_05.txt | WA | 197 ms | 29000 KB |
scrambled_06.txt | WA | 209 ms | 30920 KB |
scrambled_07.txt | WA | 196 ms | 30792 KB |
scrambled_08.txt | WA | 210 ms | 27752 KB |
scrambled_09.txt | WA | 196 ms | 25812 KB |
scrambled_10.txt | WA | 208 ms | 26836 KB |
scrambled_11.txt | TLE | 5262 ms | 342076 KB |
scrambled_12.txt | TLE | 5262 ms | 348272 KB |
scrambled_13.txt | TLE | 5267 ms | 374764 KB |
scrambled_14.txt | TLE | 5262 ms | 344612 KB |
scrambled_15.txt | TLE | 5262 ms | 341684 KB |
scrambled_16.txt | TLE | 5262 ms | 340916 KB |
scrambled_17.txt | TLE | 5262 ms | 341008 KB |
scrambled_18.txt | TLE | 5263 ms | 248444 KB |
scrambled_19.txt | TLE | 5262 ms | 340520 KB |
scrambled_20.txt | TLE | 5262 ms | 343432 KB |
scrambled_21.txt | TLE | 5258 ms | 362332 KB |
scrambled_22.txt | AC | 206 ms | 28752 KB |
scrambled_23.txt | AC | 200 ms | 31028 KB |
scrambled_24.txt | AC | 203 ms | 26220 KB |
scrambled_25.txt | AC | 197 ms | 30932 KB |
scrambled_26.txt | AC | 201 ms | 26564 KB |
scrambled_27.txt | TLE | 5262 ms | 341428 KB |
scrambled_28.txt | TLE | 5262 ms | 344200 KB |
scrambled_29.txt | TLE | 5262 ms | 342148 KB |
scrambled_30.txt | TLE | 5261 ms | 245844 KB |
scrambled_31.txt | TLE | 5262 ms | 342056 KB |
scrambled_32.txt | AC | 140 ms | 26324 KB |
subtask_00.txt | AC | 153 ms | 24660 KB |
subtask_01.txt | WA | 209 ms | 26452 KB |
subtask_02.txt | WA | 220 ms | 30440 KB |
subtask_03.txt | WA | 196 ms | 27856 KB |
subtask_04.txt | WA | 204 ms | 29908 KB |
subtask_05.txt | WA | 211 ms | 27976 KB |
subtask_06.txt | WA | 206 ms | 28872 KB |
subtask_07.txt | WA | 210 ms | 28228 KB |
subtask_08.txt | WA | 210 ms | 28772 KB |
subtask_09.txt | WA | 204 ms | 28884 KB |
subtask_10.txt | WA | 208 ms | 28372 KB |
subtask_11.txt | AC | 213 ms | 26708 KB |
subtask_12.txt | AC | 211 ms | 28628 KB |
subtask_13.txt | AC | 208 ms | 26196 KB |
subtask_14.txt | AC | 207 ms | 30676 KB |
subtask_15.txt | AC | 207 ms | 27860 KB |
subtask_16.txt | AC | 150 ms | 28244 KB |