Submission #1194965
Source Code Expand
import java.io.PrintWriter; import java.util.ArrayList; import java.util.Scanner; public class Main { static Scanner sc = new Scanner(System.in); static ArrayList<ArrayList<Integer>> g = new ArrayList<>(); static int[] dist, color, visited; static int visitedCount = 0; public static void main(String[] args) { int N = sc.nextInt(); int M = sc.nextInt(); dist = new int[N]; color = new int[N]; visited = new int[N]; for (int i = 0; i < N; i++) { g.add(new ArrayList<Integer>()); dist[i] = -1; } for (int i = 0; i < M; i++) { int A = Integer.parseInt(sc.next()) - 1; int B = Integer.parseInt(sc.next()) - 1; g.get(A).add(B); g.get(B).add(A); } int Q = sc.nextInt(); int[] V = new int[Q]; int[] D = new int[Q]; int[] C = new int[Q]; for (int i = 0; i < Q; i++) { V[i] = Integer.parseInt(sc.next()) - 1; D[i] = Integer.parseInt(sc.next()); C[i] = Integer.parseInt(sc.next()); } for (int i = Q - 1; i >= 0; i--) { update(V[i], C[i], D[i]); } PrintWriter writer = new PrintWriter(System.out); for (int i = 0; i < N; i++) { writer.println(color[i]); } writer.flush(); } static void update(int v, int c, int d) { visitedCount++; ArrayList<Integer> cur = new ArrayList<>(); cur.add(v); while (d >= 0) { ArrayList<Integer> next = new ArrayList<>(); for (int i = 0; i < cur.size(); i++) { int p = cur.get(i); if (dist[p] >= d) continue; dist[p] = d; if (color[p] == 0) color[p] = c; for (int n : g.get(p)) { if (visited[n] == visitedCount) continue; visited[n] = visitedCount; next.add(n); } } --d; cur = next; } } }
Submission Info
Submission Time | |
---|---|
Task | B - Splatter Painting |
User | tomerun |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 1873 Byte |
Status | AC |
Exec Time | 1960 ms |
Memory | 107848 KB |
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 | 129 ms | 21332 KB |
00_example_02.txt | AC | 108 ms | 20564 KB |
10_01.txt | AC | 155 ms | 22476 KB |
10_02.txt | AC | 110 ms | 19796 KB |
10_03.txt | AC | 115 ms | 21460 KB |
10_04.txt | AC | 110 ms | 21716 KB |
10_05.txt | AC | 161 ms | 23376 KB |
10_06.txt | AC | 118 ms | 21460 KB |
10_07.txt | AC | 128 ms | 20692 KB |
10_08.txt | AC | 198 ms | 28320 KB |
10_09.txt | AC | 197 ms | 25980 KB |
10_10.txt | AC | 200 ms | 26496 KB |
10_11.txt | AC | 199 ms | 28168 KB |
10_12.txt | AC | 203 ms | 27440 KB |
10_13.txt | AC | 174 ms | 23876 KB |
10_14.txt | AC | 178 ms | 24300 KB |
10_15.txt | AC | 181 ms | 25924 KB |
10_16.txt | AC | 203 ms | 28360 KB |
10_17.txt | AC | 205 ms | 28580 KB |
20_01.txt | AC | 1960 ms | 105628 KB |
20_02.txt | AC | 1098 ms | 104464 KB |
20_03.txt | AC | 1098 ms | 106112 KB |
20_04.txt | AC | 452 ms | 46752 KB |
20_05.txt | AC | 227 ms | 32660 KB |
20_06.txt | AC | 304 ms | 44868 KB |
20_07.txt | AC | 761 ms | 35952 KB |
20_08.txt | AC | 570 ms | 63428 KB |
20_09.txt | AC | 215 ms | 33552 KB |
20_10.txt | AC | 533 ms | 62680 KB |
20_11.txt | AC | 562 ms | 62684 KB |
20_12.txt | AC | 864 ms | 73044 KB |
20_13.txt | AC | 884 ms | 103508 KB |
20_14.txt | AC | 987 ms | 104628 KB |
20_15.txt | AC | 1004 ms | 105876 KB |
20_16.txt | AC | 1078 ms | 107848 KB |