Submission #58428
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int kInf = 0xFFFF; int main() { int n; cin >> n; if (n > 50) return true; vector<int> c(n), p(n); p[0] = -1; cin >> c[0]; for (int i = 1; i < n; i++) { cin >> p[i] >> c[i]; --p[i]; } for (int i = 0; i < n; i++) { c[i] += 50; } vector< vector<int> > dp(n); for (int i = n - 1; i >= 0; i--) { dp[i] = vector<int>(101); for (int j = 0; j <= 100; j++) { dp[i][j] = abs(c[i] - j); for (int k = i + 1; k < n; k++) { if (p[k] != i) continue; int m = kInf; for (int l = 0; l < j; l++) { m = min(m, dp[k][l]); } dp[i][j] += m; } } } cout << *min_element(dp[0].begin(), dp[0].end()) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | L - じょうしょうツリー |
User | yuizumi |
Language | C++ (G++ 4.6.4) |
Score | 50 |
Code Size | 901 Byte |
Status | WA |
Exec Time | 24 ms |
Memory | 832 KB |
Judge Result
Set Name | Set 01 | Set 02 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 0 / 250 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Set 01 | 00_sample1.txt, 00_sample2.txt, 01_000_random_N21_C50.txt, 01_001_random_N1_C50.txt, 01_002_random_N17_C50.txt, 01_003_random_N47_C50.txt, 01_004_random_N2_C50.txt, 01_005_random_N50_C50.txt, 01_006_random_N17_C50.txt, 01_007_random_N6_C50.txt, 01_008_random_N4_C50.txt, 01_009_random_N16_C50.txt, 01_010_random_N22_C50.txt, 01_011_random_N24_C50.txt, 01_012_random_N2_C50.txt, 01_013_random_N49_C50.txt, 01_014_random_N24_C50.txt, 01_015_random_N30_C50.txt, 01_016_random_N16_C50.txt, 01_017_random_N33_C50.txt, 01_018_random_N14_C50.txt, 01_019_random_N18_C50.txt, 01_020_random_N21_C50.txt, 01_021_random_N12_C50.txt, 01_022_random_N18_C50.txt, 01_023_random_N27_C50.txt, 01_024_random_N41_C50.txt, 01_025_random_N33_C50.txt, 01_026_random_N3_C50.txt, 01_027_random_N4_C50.txt, 01_028_random_N1_C50.txt, 01_029_random_N11_C50.txt |
Set 02 | 00_sample1.txt, 00_sample2.txt, 01_000_random_N21_C50.txt, 01_001_random_N1_C50.txt, 01_002_random_N17_C50.txt, 01_003_random_N47_C50.txt, 01_004_random_N2_C50.txt, 01_005_random_N50_C50.txt, 01_006_random_N17_C50.txt, 01_007_random_N6_C50.txt, 01_008_random_N4_C50.txt, 01_009_random_N16_C50.txt, 01_010_random_N22_C50.txt, 01_011_random_N24_C50.txt, 01_012_random_N2_C50.txt, 01_013_random_N49_C50.txt, 01_014_random_N24_C50.txt, 01_015_random_N30_C50.txt, 01_016_random_N16_C50.txt, 01_017_random_N33_C50.txt, 01_018_random_N14_C50.txt, 01_019_random_N18_C50.txt, 01_020_random_N21_C50.txt, 01_021_random_N12_C50.txt, 01_022_random_N18_C50.txt, 01_023_random_N27_C50.txt, 01_024_random_N41_C50.txt, 01_025_random_N33_C50.txt, 01_026_random_N3_C50.txt, 01_027_random_N4_C50.txt, 01_028_random_N1_C50.txt, 01_029_random_N11_C50.txt, 02_000_random_N69_C1000000000.txt, 02_001_random_N47_C1000000000.txt, 02_002_random_N67_C1000000000.txt, 02_003_random_N43_C1000000000.txt, 02_004_random_N83_C1000000000.txt, 02_005_random_N89_C1000000000.txt, 02_006_random_N86_C1000000000.txt, 02_007_random_N4_C1000000000.txt, 02_008_random_N94_C1000000000.txt, 02_009_random_N36_C1000000000.txt, 02_010_random_N85_C1000000000.txt, 02_011_random_N17_C1000000000.txt, 02_012_random_N65_C1000000000.txt, 02_013_random_N9_C1000000000.txt, 02_014_random_N68_C1000000000.txt, 02_015_random_N91_C1000000000.txt, 02_016_random_N39_C1000000000.txt, 02_017_random_N57_C1000000000.txt, 02_018_random_N76_C1000000000.txt, 02_019_random_N87_C1000000000.txt, 02_020_random_N36_C1000000000.txt, 02_021_random_N9_C1000000000.txt, 02_022_random_N66_C1000000000.txt, 02_023_random_N67_C1000000000.txt, 02_024_random_N60_C1000000000.txt, 02_025_random_N29_C1000000000.txt, 02_026_random_N92_C1000000000.txt, 02_027_random_N77_C1000000000.txt, 02_028_random_N17_C1000000000.txt, 02_029_random_N28_C1000000000.txt, 02_030_random_1000000000_random_100000.txt, 02_031_random_1000000000_bigd_100000_90000, 02_032_increasing_1000000000_0_random_100000.txt, 02_033_increasing_1000000000_0_bigd_100000_90000, 02_034_increasing_1000000000_30_random_100000.txt, 02_035_increasing_1000000000_30_bigd_100000_90000, 02_036_increasing_1000000000_1000_random_100000.txt, 02_037_increasing_1000000000_1000_bigd_100000_90000, 02_038_increasing_1000000000_10000_random_100000.txt, 02_039_increasing_1000000000_10000_bigd_100000_90000, 02_040_random_1000000000_bigd_100000_50000, 02_041_random_1000000000_bigd_100000_99999, 02_042_random_1000000000_star_100000_4_10000.txt, 02_043_random_1000000000_star_100000_30_3000.txt, 02_044_random_1000000000_longpath-heavyroot_100000_90000, 02_045_increasing_1000000000_50_bigd_100000_50000, 02_046_increasing_1000000000_50_bigd_100000_99999, 02_047_increasing_1000000000_50_star_100000_4_10000.txt, 02_048_increasing_1000000000_50_star_100000_30_3000.txt, 02_049_increasing_1000000000_50_longpath-heavyroot_100000_90000 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample1.txt | AC | 21 ms | 780 KB |
00_sample2.txt | AC | 19 ms | 784 KB |
01_000_random_N21_C50.txt | AC | 21 ms | 696 KB |
01_001_random_N1_C50.txt | AC | 19 ms | 784 KB |
01_002_random_N17_C50.txt | AC | 19 ms | 784 KB |
01_003_random_N47_C50.txt | AC | 20 ms | 768 KB |
01_004_random_N2_C50.txt | AC | 20 ms | 656 KB |
01_005_random_N50_C50.txt | AC | 21 ms | 652 KB |
01_006_random_N17_C50.txt | AC | 21 ms | 780 KB |
01_007_random_N6_C50.txt | AC | 20 ms | 792 KB |
01_008_random_N4_C50.txt | AC | 21 ms | 704 KB |
01_009_random_N16_C50.txt | AC | 21 ms | 632 KB |
01_010_random_N22_C50.txt | AC | 21 ms | 788 KB |
01_011_random_N24_C50.txt | AC | 19 ms | 816 KB |
01_012_random_N2_C50.txt | AC | 21 ms | 780 KB |
01_013_random_N49_C50.txt | AC | 20 ms | 780 KB |
01_014_random_N24_C50.txt | AC | 19 ms | 784 KB |
01_015_random_N30_C50.txt | AC | 21 ms | 788 KB |
01_016_random_N16_C50.txt | AC | 21 ms | 780 KB |
01_017_random_N33_C50.txt | AC | 22 ms | 784 KB |
01_018_random_N14_C50.txt | AC | 20 ms | 788 KB |
01_019_random_N18_C50.txt | AC | 21 ms | 788 KB |
01_020_random_N21_C50.txt | AC | 21 ms | 784 KB |
01_021_random_N12_C50.txt | AC | 20 ms | 784 KB |
01_022_random_N18_C50.txt | AC | 19 ms | 792 KB |
01_023_random_N27_C50.txt | AC | 23 ms | 832 KB |
01_024_random_N41_C50.txt | AC | 22 ms | 632 KB |
01_025_random_N33_C50.txt | AC | 20 ms | 780 KB |
01_026_random_N3_C50.txt | AC | 20 ms | 696 KB |
01_027_random_N4_C50.txt | AC | 24 ms | 788 KB |
01_028_random_N1_C50.txt | AC | 19 ms | 784 KB |
01_029_random_N11_C50.txt | AC | 20 ms | 760 KB |
02_000_random_N69_C1000000000.txt | RE | 20 ms | 660 KB |
02_001_random_N47_C1000000000.txt | WA | 20 ms | 784 KB |
02_002_random_N67_C1000000000.txt | RE | 20 ms | 656 KB |
02_003_random_N43_C1000000000.txt | WA | 21 ms | 788 KB |
02_004_random_N83_C1000000000.txt | RE | 21 ms | 700 KB |
02_005_random_N89_C1000000000.txt | RE | 21 ms | 788 KB |
02_006_random_N86_C1000000000.txt | RE | 21 ms | 788 KB |
02_007_random_N4_C1000000000.txt | WA | 20 ms | 784 KB |
02_008_random_N94_C1000000000.txt | RE | 19 ms | 780 KB |
02_009_random_N36_C1000000000.txt | WA | 21 ms | 780 KB |
02_010_random_N85_C1000000000.txt | RE | 20 ms | 632 KB |
02_011_random_N17_C1000000000.txt | WA | 21 ms | 696 KB |
02_012_random_N65_C1000000000.txt | RE | 20 ms | 792 KB |
02_013_random_N9_C1000000000.txt | WA | 19 ms | 780 KB |
02_014_random_N68_C1000000000.txt | RE | 19 ms | 780 KB |
02_015_random_N91_C1000000000.txt | RE | 20 ms | 640 KB |
02_016_random_N39_C1000000000.txt | WA | 21 ms | 788 KB |
02_017_random_N57_C1000000000.txt | RE | 20 ms | 780 KB |
02_018_random_N76_C1000000000.txt | RE | 20 ms | 692 KB |
02_019_random_N87_C1000000000.txt | RE | 21 ms | 784 KB |
02_020_random_N36_C1000000000.txt | WA | 19 ms | 792 KB |
02_021_random_N9_C1000000000.txt | WA | 19 ms | 780 KB |
02_022_random_N66_C1000000000.txt | RE | 19 ms | 784 KB |
02_023_random_N67_C1000000000.txt | RE | 18 ms | 788 KB |
02_024_random_N60_C1000000000.txt | RE | 19 ms | 784 KB |
02_025_random_N29_C1000000000.txt | WA | 20 ms | 800 KB |
02_026_random_N92_C1000000000.txt | RE | 20 ms | 784 KB |
02_027_random_N77_C1000000000.txt | RE | 18 ms | 656 KB |
02_028_random_N17_C1000000000.txt | WA | 19 ms | 788 KB |
02_029_random_N28_C1000000000.txt | WA | 21 ms | 784 KB |
02_030_random_1000000000_random_100000.txt | RE | 22 ms | 796 KB |
02_031_random_1000000000_bigd_100000_90000 | RE | 20 ms | 792 KB |
02_032_increasing_1000000000_0_random_100000.txt | RE | 22 ms | 652 KB |
02_033_increasing_1000000000_0_bigd_100000_90000 | RE | 19 ms | 788 KB |
02_034_increasing_1000000000_30_random_100000.txt | RE | 21 ms | 792 KB |
02_035_increasing_1000000000_30_bigd_100000_90000 | RE | 19 ms | 784 KB |
02_036_increasing_1000000000_1000_random_100000.txt | RE | 21 ms | 780 KB |
02_037_increasing_1000000000_1000_bigd_100000_90000 | RE | 19 ms | 792 KB |
02_038_increasing_1000000000_10000_random_100000.txt | RE | 23 ms | 784 KB |
02_039_increasing_1000000000_10000_bigd_100000_90000 | RE | 18 ms | 780 KB |
02_040_random_1000000000_bigd_100000_50000 | RE | 20 ms | 788 KB |
02_041_random_1000000000_bigd_100000_99999 | RE | 21 ms | 764 KB |
02_042_random_1000000000_star_100000_4_10000.txt | RE | 20 ms | 788 KB |
02_043_random_1000000000_star_100000_30_3000.txt | RE | 21 ms | 696 KB |
02_044_random_1000000000_longpath-heavyroot_100000_90000 | RE | 21 ms | 784 KB |
02_045_increasing_1000000000_50_bigd_100000_50000 | RE | 20 ms | 784 KB |
02_046_increasing_1000000000_50_bigd_100000_99999 | RE | 22 ms | 736 KB |
02_047_increasing_1000000000_50_star_100000_4_10000.txt | RE | 19 ms | 792 KB |
02_048_increasing_1000000000_50_star_100000_30_3000.txt | RE | 21 ms | 780 KB |
02_049_increasing_1000000000_50_longpath-heavyroot_100000_90000 | RE | 21 ms | 808 KB |