Submission #773529
Source Code Expand
import std.stdio; import std.algorithm; import std.string; import std.range; import std.array; import std.conv; import std.complex; import std.math; import std.ascii; import std.bigint; import std.container; import std.typecons; auto readInts() { return array(map!(to!int)(readln().strip().split())); } auto readInt() { return readInts()[0]; } auto readLongs() { return array(map!(to!long)(readln().strip().split())); } auto readLong() { return readLongs()[0]; } void readlnTo(T...)(ref T t) { auto s = readln().split(); assert(s.length == t.length); foreach(ref ti; t) { ti = s[0].to!(typeof(ti)); s = s[1..$]; } } const real eps = 1e-10; void main(){ int n, m; readlnTo(n, m); auto e = new RedBlackTree!(int[], "a > b"); foreach(i; iota(m)) { int a, b, y; readlnTo(a, b, y); e.insert([y, a-1, b-1]); } auto q = readInt(); int[][] p; foreach(i; iota(q)) { int v, w; readlnTo(v, w); p ~= [w, v-1, i]; } p.sort!("a > b")(); auto ans = new int[](q); RedBlackTree!int[] c; foreach(i; iota(n)) { c ~= redBlackTree(i.to!int); } auto d = iota(n).array; foreach(i; iota(q)) { auto w = p[i][0]; auto v = p[i][1]; auto qi = p[i][2]; while(!e.empty && w < e.front[0]) { auto a = e.front[1]; auto b = e.front[2]; e.removeFront(); if(d[a] == d[b]) { continue; } if(c[d[a]].length < c[d[b]].length) { swap(a,b); } c[d[a]].insert(c[d[b]][]); foreach(cbi; c[d[b]]) { d[cbi] = d[a]; } } ans[qi] = c[d[v]].length.to!int; } ans.each!(writeln); }
Submission Info
Submission Time | |
---|---|
Task | D - 道路の老朽化対策について |
User | tsuburin |
Language | D (DMD64 v2.070.1) |
Score | 100 |
Code Size | 1897 Byte |
Status | AC |
Exec Time | 1331 ms |
Memory | 44796 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 4 ms | 256 KB |
sample_02.txt | AC | 4 ms | 256 KB |
sample_03.txt | AC | 4 ms | 256 KB |
subtask1_01.txt | AC | 13 ms | 764 KB |
subtask1_02.txt | AC | 13 ms | 764 KB |
subtask1_03.txt | AC | 13 ms | 764 KB |
subtask1_04.txt | AC | 9 ms | 636 KB |
subtask1_05.txt | AC | 13 ms | 764 KB |
subtask1_06.txt | AC | 13 ms | 764 KB |
subtask1_07.txt | AC | 13 ms | 764 KB |
subtask2_01.txt | AC | 1331 ms | 44668 KB |
subtask2_02.txt | AC | 1287 ms | 44668 KB |
subtask2_03.txt | AC | 1279 ms | 44668 KB |
subtask2_04.txt | AC | 1304 ms | 44540 KB |
subtask2_05.txt | AC | 627 ms | 29692 KB |
subtask2_06.txt | AC | 1233 ms | 44156 KB |
subtask2_07.txt | AC | 1248 ms | 44156 KB |
subtask2_08.txt | AC | 1255 ms | 44156 KB |
subtask2_09.txt | AC | 1303 ms | 44796 KB |
subtask2_10.txt | AC | 1289 ms | 44412 KB |
subtask2_11.txt | AC | 1295 ms | 43900 KB |
subtask2_12.txt | AC | 1202 ms | 43772 KB |