Submission #1196689
Source Code Expand
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;
public class Program
{
int N, M;
int[][] E, Q;
int[] Color;
int[] MaxRemDist;
public void Solve()
{
N = Reader.Int();
M = Reader.Int();
E = EdgeRead(N, M);
int NQ = Reader.Int();
Q = Reader.IntTable(NQ);
foreach (var q in Q) q[0]--;
Color = new int[N];
MaxRemDist = Enu.Repeat(-1, N).ToArray();
Array.Reverse(Q);
foreach (var q in Q)
BFS(q[0], q[1], q[2]);
Console.WriteLine(string.Join("\n", Color));
}
void BFS(int start, int D, int C)
{
if (MaxRemDist[start] >= D) return;
var que = new Queue<int>();
que.Enqueue(start);
if (MaxRemDist[start] < 0) Color[start] = C;
MaxRemDist[start] = D;
for (; D > 0; D--)
{
var nextQue = new Queue<int>();
while (que.Count > 0)
{
int at = que.Dequeue();
foreach (int next in E[at])
if (D - 1 > MaxRemDist[next])
{
if (MaxRemDist[next] < 0) Color[next] = C;
MaxRemDist[next] = Math.Max(MaxRemDist[next], D - 1);
nextQue.Enqueue(next);
}
}
que = nextQue;
}
}
int[][] EdgeRead(int V, int E = -1, int origin = 1)
{
if (E == -1) E = V - 1;
var es = new List<int>[V];
for (int i = 0; i < V; i++) es[i] = new List<int>();
for (int i = 0; i < E; i++)
{
int a = Reader.Int() - origin, b = Reader.Int() - origin;
es[a].Add(b);
es[b].Add(a);
}
return es.Select(a => a.ToArray()).ToArray();
}
}
class RangeUpdateSumSegTree
{
public readonly int N;
private readonly long[] V, S;
private readonly bool[] Flag;
public RangeUpdateSumSegTree(int n)
{
for (N = 2; N < n; ) N *= 2;
V = new long[N * 2];
S = new long[N * 2];
Flag = new bool[N * 2];
}
public long Sum(int L, int R) { return Sum(0, 0, N, L, R); }
private long Sum(int i, int currL, int currR, int L, int R)
{
if (currL >= R || currR <= L) return 0;
if (currL >= L && currR <= R) return S[i];
if (Flag[i]) return V[i] * (Math.Min(currR, R) - Math.Max(currL, L));
int mid = (currL + currR) / 2;
long valL = Sum(i * 2 + 1, currL, mid, L, R);
long valR = Sum(i * 2 + 2, mid, currR, L, R);
return valL + valR;
}
public void Update(int L, int R, long val) { Update(0, val, 0, N, L, R); }
private void Update(int i, long val, int currL, int currR, int L, int R)
{
if (currL >= R || currR <= L) return;
if (currL >= L && currR <= R)
{
Flag[i] = true;
V[i] = val;
S[i] = val * (currR - currL);
return;
}
if (Flag[i] && currR - currL > 1)
{
V[i * 2 + 1] = V[i * 2 + 2] = V[i];
S[i * 2 + 1] = S[i * 2 + 2] = (currR - currL) / 2 * V[i];
Flag[i * 2 + 1] = Flag[i * 2 + 2] = true;
Flag[i] = false;
}
int mid = (currL + currR) / 2;
Update(i * 2 + 1, val, currL, mid, L, R);
Update(i * 2 + 2, val, mid, currR, L, R);
S[i] = S[i * 2 + 1] + S[i * 2 + 2];
}
}
class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
static TextReader reader = Console.In;
static readonly char[] separator = { ' ' };
static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
static string[] A = new string[0];
static int i;
static void Init() { A = new string[0]; }
public static void Set(TextReader r) { reader = r; Init(); }
public static void Set(string file) { reader = new StreamReader(file); Init(); }
public static bool HasNext() { return CheckNext(); }
public static string String() { return Next(); }
public static int Int() { return int.Parse(Next()); }
public static long Long() { return long.Parse(Next()); }
public static double Double() { return double.Parse(Next()); }
public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
public static int[] IntArray(int N) { return Range(N, Int); }
public static int[][] IntTable(int H) { return Range(H, IntLine); }
public static string[] StringArray(int N) { return Range(N, Next); }
public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
public static string Line() { return reader.ReadLine().Trim(); }
public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
static string[] Split(string s) { return s.Split(separator, op); }
static string Next() { CheckNext(); return A[i++]; }
static bool CheckNext()
{
if (i < A.Length) return true;
string line = reader.ReadLine();
if (line == null) return false;
if (line == "") return CheckNext();
A = Split(line);
i = 0;
return true;
}
}
Submission Info
Submission Time |
|
Task |
B - Splatter Painting |
User |
eitaho |
Language |
C# (Mono 4.6.2.0) |
Score |
700 |
Code Size |
5503 Byte |
Status |
AC |
Exec Time |
390 ms |
Memory |
43900 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 |
30 ms |
11604 KB |
00_example_02.txt |
AC |
30 ms |
13652 KB |
10_01.txt |
AC |
31 ms |
11604 KB |
10_02.txt |
AC |
30 ms |
9556 KB |
10_03.txt |
AC |
30 ms |
11604 KB |
10_04.txt |
AC |
30 ms |
13652 KB |
10_05.txt |
AC |
31 ms |
9556 KB |
10_06.txt |
AC |
30 ms |
11604 KB |
10_07.txt |
AC |
30 ms |
9600 KB |
10_08.txt |
AC |
35 ms |
9628 KB |
10_09.txt |
AC |
35 ms |
9532 KB |
10_10.txt |
AC |
36 ms |
11572 KB |
10_11.txt |
AC |
35 ms |
11572 KB |
10_12.txt |
AC |
36 ms |
9628 KB |
10_13.txt |
AC |
33 ms |
9556 KB |
10_14.txt |
AC |
33 ms |
11604 KB |
10_15.txt |
AC |
32 ms |
9564 KB |
10_16.txt |
AC |
35 ms |
11640 KB |
10_17.txt |
AC |
36 ms |
9612 KB |
20_01.txt |
AC |
371 ms |
37260 KB |
20_02.txt |
AC |
390 ms |
37388 KB |
20_03.txt |
AC |
373 ms |
35208 KB |
20_04.txt |
AC |
76 ms |
17496 KB |
20_05.txt |
AC |
38 ms |
13716 KB |
20_06.txt |
AC |
75 ms |
29044 KB |
20_07.txt |
AC |
39 ms |
11656 KB |
20_08.txt |
AC |
121 ms |
18892 KB |
20_09.txt |
AC |
38 ms |
11668 KB |
20_10.txt |
AC |
121 ms |
17228 KB |
20_11.txt |
AC |
151 ms |
22596 KB |
20_12.txt |
AC |
211 ms |
32544 KB |
20_13.txt |
AC |
316 ms |
32712 KB |
20_14.txt |
AC |
333 ms |
32416 KB |
20_15.txt |
AC |
332 ms |
35320 KB |
20_16.txt |
AC |
361 ms |
43900 KB |