Submission #1196810


Source Code Expand

Copy
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		V[] vs = new V[N];
		for (int i = 0; i < N; i++) {
			vs[i] = new V(i);
		}
		for (int i = 0; i < M; i++) {
			int s = sc.nextInt() - 1;
			int t = sc.nextInt() - 1;
			vs[s].add(t);
			vs[t].add(s);
		}
		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] = sc.nextInt() - 1;
			d[i] = sc.nextInt();
			c[i] = sc.nextInt();
		}
		dist = new int[N];
		Arrays.fill(dist, -1);
		for (int i = Q - 1; i >= 0; i--) {
			color(vs, v[i], d[i], c[i]);
		}
		Arrays.stream(vs).forEach(u -> System.out.println(u.col));
	}
	static int dist[];
	private static void color(V[] vs, int s, int d, int c) {
		if (dist[s] >= d) {
			return;
		}
		Queue<Integer> que = new LinkedList<>();
		que.add(s);
		dist[s] = d;
		while(que.isEmpty() == false) {
			int u = que.poll();
			if (vs[u].col == 0) { 
				vs[u].col = c;
			}
			if (dist[u] == 0) {
				continue;
			}
			for (int v: vs[u]) {
				if (dist[v] >= dist[u] - 1) {
					continue;
				}
				que.add(v);
				dist[v] = dist[u] - 1;
			}
		}
	}
	static class V extends ArrayList<Integer>{
		int id;
		int col = 0;
		V(int _id) {
			id = _id;
		}
	}
}

Submission Info

Submission Time
Task B - Splatter Painting
User zosan
Language Java8 (OpenJDK 1.8.0)
Score 700
Code Size 1407 Byte
Status
Exec Time 1476 ms
Memory 170224 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt
Subtask1 200 / 200 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 500 / 500 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 282 ms 31316 KB
00_example_02.txt 179 ms 26708 KB
10_01.txt 233 ms 27704 KB
10_02.txt 186 ms 27092 KB
10_03.txt 188 ms 25552 KB
10_04.txt 172 ms 27220 KB
10_05.txt 224 ms 28452 KB
10_06.txt 184 ms 24656 KB
10_07.txt 214 ms 24912 KB
10_08.txt 334 ms 33388 KB
10_09.txt 315 ms 33308 KB
10_10.txt 336 ms 33004 KB
10_11.txt 341 ms 35128 KB
10_12.txt 336 ms 34976 KB
10_13.txt 286 ms 31820 KB
10_14.txt 301 ms 29036 KB
10_15.txt 289 ms 33108 KB
10_16.txt 323 ms 33460 KB
10_17.txt 336 ms 32820 KB
20_01.txt 1426 ms 170184 KB
20_02.txt 1431 ms 169108 KB
20_03.txt 1446 ms 165504 KB
20_04.txt 631 ms 62652 KB
20_05.txt 344 ms 42768 KB
20_06.txt 799 ms 46732 KB
20_07.txt 367 ms 39440 KB
20_08.txt 638 ms 90168 KB
20_09.txt 354 ms 41204 KB
20_10.txt 619 ms 65928 KB
20_11.txt 713 ms 92472 KB
20_12.txt 1167 ms 102620 KB
20_13.txt 1280 ms 146520 KB
20_14.txt 1323 ms 170224 KB
20_15.txt 1476 ms 169076 KB
20_16.txt 1452 ms 169680 KB