Submission #1194615
Source Code Expand
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.io.BufferedWriter; import java.util.InputMismatchException; import java.io.IOException; import java.util.ArrayList; import java.util.List; import java.util.stream.Stream; 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) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); OutputWriter out = new OutputWriter(outputStream); TaskB solver = new TaskB(); solver.solve(1, in, out); out.close(); } static class TaskB { public List<Integer>[] graph; public int[] color; public int[] maxx; public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.nextInt(), m = in.nextInt(); graph = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new); for (int i = 0; i < m; i++) { int a = in.nextInt() - 1, b = in.nextInt() - 1; graph[a].add(b); graph[b].add(a); } int q = in.nextInt(); color = new int[n]; int[] v = new int[q], d = new int[q], c = new int[q]; for (int i = 0; i < q; i++) { v[i] = in.nextInt() - 1; d[i] = in.nextInt(); c[i] = in.nextInt(); } maxx = new int[n]; Arrays.fill(maxx, -1); for (int i = q - 1; i >= 0; i--) { process(v[i], d[i], c[i]); } out.println(color); } public void process(int v, int dist, int c) { if (dist <= maxx[v]) return; maxx[v] = dist; if (color[v] == 0) color[v] = c; for (int next : graph[v]) { process(next, dist - 1, c); } } } static class OutputWriter { private final PrintWriter writer; public OutputWriter(OutputStream outputStream) { writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); } public OutputWriter(Writer writer) { this.writer = new PrintWriter(writer); } public void print(int[] array) { for (int i = 0; i < array.length; i++) { if (i != 0) { writer.print(' '); } writer.print(array[i]); } } public void println(int[] array) { print(array); writer.println(); } public void close() { writer.close(); } } static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } public int read() { if (this.numChars == -1) { throw new InputMismatchException(); } else { if (this.curChar >= this.numChars) { this.curChar = 0; try { this.numChars = this.stream.read(this.buf); } catch (IOException var2) { throw new InputMismatchException(); } if (this.numChars <= 0) { return -1; } } return this.buf[this.curChar++]; } } public int nextInt() { int c; for (c = this.read(); isSpaceChar(c); c = this.read()) { ; } byte sgn = 1; if (c == 45) { sgn = -1; c = this.read(); } int res = 0; while (c >= 48 && c <= 57) { res *= 10; res += c - 48; c = this.read(); if (isSpaceChar(c)) { return res * sgn; } } throw new InputMismatchException(); } public static boolean isSpaceChar(int c) { return c == 32 || c == 10 || c == 13 || c == 9 || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | lewin |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 4811 Byte |
Status | AC |
Exec Time | 460 ms |
Memory | 67588 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt |
All | 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt, 20_01.txt, 20_02.txt, 20_03.txt, 20_04.txt, 20_05.txt, 20_06.txt, 20_07.txt, 20_08.txt, 20_09.txt, 20_10.txt, 20_11.txt, 20_12.txt, 20_13.txt, 20_14.txt, 20_15.txt, 20_16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 403 ms | 25172 KB |
00_example_02.txt | AC | 158 ms | 23508 KB |
10_01.txt | AC | 171 ms | 24660 KB |
10_02.txt | AC | 154 ms | 28372 KB |
10_03.txt | AC | 158 ms | 26580 KB |
10_04.txt | AC | 212 ms | 25424 KB |
10_05.txt | AC | 180 ms | 24392 KB |
10_06.txt | AC | 168 ms | 22612 KB |
10_07.txt | AC | 166 ms | 26580 KB |
10_08.txt | AC | 190 ms | 24532 KB |
10_09.txt | AC | 190 ms | 26452 KB |
10_10.txt | AC | 178 ms | 25680 KB |
10_11.txt | AC | 178 ms | 23892 KB |
10_12.txt | AC | 198 ms | 24660 KB |
10_13.txt | AC | 174 ms | 24276 KB |
10_14.txt | AC | 172 ms | 26452 KB |
10_15.txt | AC | 175 ms | 24660 KB |
10_16.txt | AC | 177 ms | 23764 KB |
10_17.txt | AC | 177 ms | 27988 KB |
20_01.txt | AC | 393 ms | 60744 KB |
20_02.txt | AC | 365 ms | 53760 KB |
20_03.txt | AC | 386 ms | 57876 KB |
20_04.txt | AC | 224 ms | 26432 KB |
20_05.txt | AC | 173 ms | 23892 KB |
20_06.txt | AC | 240 ms | 31572 KB |
20_07.txt | AC | 184 ms | 23764 KB |
20_08.txt | AC | 214 ms | 22864 KB |
20_09.txt | AC | 178 ms | 24524 KB |
20_10.txt | AC | 452 ms | 23760 KB |
20_11.txt | AC | 216 ms | 26960 KB |
20_12.txt | AC | 308 ms | 50500 KB |
20_13.txt | AC | 329 ms | 54868 KB |
20_14.txt | AC | 345 ms | 51036 KB |
20_15.txt | AC | 379 ms | 60428 KB |
20_16.txt | AC | 460 ms | 67588 KB |