Submission #2441900
Source Code Expand
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { auto N = readln.chomp.to!int; auto E = new Tuple!(int, int)[](N-1); auto G = new Tuple!(int, int)[][](N); foreach (i; 0..N-1) { auto s = readln.split.map!(to!int); G[s[0]-1] ~= tuple(s[1]-1, i); G[s[1]-1] ~= tuple(s[0]-1, i); E[i] = tuple(s[0]-1, s[1]-1); } auto S = readln.split.map!(to!long).array; if (N == 2) { writeln(S[0]); return; } auto depth = new int[](N); auto sub = new int[](N); auto ans = new long[](N-1); int dfs(int n, int p, int d) { depth[n] = d; foreach (m; G[n]) if (m[0] != p) sub[n] += dfs(m[0], n, d+1); return sub[n] + 1; } dfs(0, -1, 0); long dfs2(int n, int p, long d) { long ret = d; foreach (m; G[n]) if (m[0] != p) ret += dfs2(m[0], n, d+ans[m[1]]); return ret; } foreach (i, e; E.enumerate) { int a = e[0]; int b = e[1]; if (S[a] == S[b]) continue; if (depth[a] > depth[b]) swap(a, b); long aa = sub[b]; long bb = N - sub[b] - 2; ans[i] = (S[a] - S[b]) / (aa - bb); } foreach (i, e; E.enumerate) { int a = e[0]; int b = e[1]; if (S[a] != S[b]) continue; if (depth[a] > depth[b]) swap(a, b); long aa = dfs2(a, b, 0); long bb = dfs2(b, a, 0); long ss = aa + bb; ans[i] = (S[a] - ss) / (sub[b] + 1); } ans.each!writeln; }
Submission Info
Submission Time | |
---|---|
Task | D - Ancient Tree Record |
User | nebukuro09 |
Language | D (LDC 0.17.0) |
Score | 800 |
Code Size | 1734 Byte |
Status | AC |
Exec Time | 179 ms |
Memory | 26812 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 200 / 200 | 300 / 300 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt |
Subtask2 | 00_example_02.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s3_27.txt, s3_28.txt, s3_29.txt, s3_30.txt, s3_31.txt, s3_32.txt, s3_33.txt, s3_34.txt, s3_35.txt, s3_36.txt, s3_37.txt, s3_38.txt, s3_39.txt, s3_40.txt, s3_41.txt, s3_42.txt, s3_43.txt, s3_44.txt, s3_45.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 1 ms | 256 KB |
00_example_02.txt | AC | 1 ms | 256 KB |
00_example_03.txt | AC | 1 ms | 256 KB |
s1_01.txt | AC | 90 ms | 19868 KB |
s1_02.txt | AC | 127 ms | 24504 KB |
s1_03.txt | AC | 6 ms | 1404 KB |
s1_04.txt | AC | 106 ms | 19664 KB |
s1_05.txt | AC | 17 ms | 4424 KB |
s1_06.txt | AC | 154 ms | 26812 KB |
s1_07.txt | AC | 156 ms | 26684 KB |
s1_08.txt | AC | 154 ms | 26044 KB |
s1_09.txt | AC | 1 ms | 256 KB |
s1_10.txt | AC | 1 ms | 256 KB |
s1_11.txt | AC | 1 ms | 256 KB |
s1_12.txt | AC | 1 ms | 256 KB |
s1_13.txt | AC | 1 ms | 256 KB |
s2_14.txt | AC | 75 ms | 12624 KB |
s2_15.txt | AC | 103 ms | 16076 KB |
s2_16.txt | AC | 131 ms | 20848 KB |
s2_17.txt | AC | 131 ms | 19440 KB |
s2_18.txt | AC | 130 ms | 18928 KB |
s2_19.txt | AC | 130 ms | 19568 KB |
s2_20.txt | AC | 1 ms | 256 KB |
s2_21.txt | AC | 1 ms | 256 KB |
s2_22.txt | AC | 1 ms | 256 KB |
s2_23.txt | AC | 1 ms | 256 KB |
s3_24.txt | AC | 92 ms | 12936 KB |
s3_25.txt | AC | 140 ms | 17364 KB |
s3_26.txt | AC | 6 ms | 1148 KB |
s3_27.txt | AC | 116 ms | 16548 KB |
s3_28.txt | AC | 17 ms | 2268 KB |
s3_29.txt | AC | 168 ms | 19656 KB |
s3_30.txt | AC | 155 ms | 19660 KB |
s3_31.txt | AC | 168 ms | 18752 KB |
s3_32.txt | AC | 167 ms | 23484 KB |
s3_33.txt | AC | 164 ms | 26428 KB |
s3_34.txt | AC | 149 ms | 20336 KB |
s3_35.txt | AC | 150 ms | 20592 KB |
s3_36.txt | AC | 1 ms | 256 KB |
s3_37.txt | AC | 1 ms | 256 KB |
s3_38.txt | AC | 1 ms | 256 KB |
s3_39.txt | AC | 1 ms | 256 KB |
s3_40.txt | AC | 93 ms | 12936 KB |
s3_41.txt | AC | 148 ms | 16844 KB |
s3_42.txt | AC | 6 ms | 1148 KB |
s3_43.txt | AC | 179 ms | 19908 KB |
s3_44.txt | AC | 164 ms | 19848 KB |
s3_45.txt | AC | 166 ms | 18888 KB |