Task: | Nice triplets |
Sender: | z |
Submission time: | 2016-09-06 18:10:21 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.07 s | details |
#3 | ACCEPTED | 0.18 s | details |
#4 | ACCEPTED | 0.19 s | details |
#5 | ACCEPTED | 0.07 s | details |
#6 | ACCEPTED | 0.09 s | details |
#7 | ACCEPTED | 0.11 s | details |
#8 | ACCEPTED | 0.10 s | details |
#9 | ACCEPTED | 0.21 s | details |
#10 | ACCEPTED | 0.05 s | details |
#11 | ACCEPTED | 0.28 s | details |
#12 | ACCEPTED | 0.28 s | details |
#13 | ACCEPTED | 0.29 s | details |
#14 | ACCEPTED | 0.28 s | details |
#15 | ACCEPTED | 0.28 s | details |
#16 | ACCEPTED | 0.21 s | details |
#17 | ACCEPTED | 0.23 s | details |
#18 | ACCEPTED | 0.20 s | details |
#19 | ACCEPTED | 0.21 s | details |
#20 | ACCEPTED | 0.21 s | details |
#21 | ACCEPTED | 0.20 s | details |
#22 | ACCEPTED | 0.29 s | details |
#23 | ACCEPTED | 0.31 s | details |
#24 | ACCEPTED | 0.30 s | details |
#25 | ACCEPTED | 0.35 s | details |
#26 | ACCEPTED | 0.34 s | details |
#27 | ACCEPTED | 0.35 s | details |
#28 | ACCEPTED | 0.34 s | details |
#29 | ACCEPTED | 0.34 s | details |
#30 | ACCEPTED | 0.34 s | details |
#31 | ACCEPTED | 0.34 s | details |
#32 | ACCEPTED | 0.35 s | details |
#33 | ACCEPTED | 0.34 s | details |
#34 | ACCEPTED | 0.34 s | details |
#35 | ACCEPTED | 0.34 s | details |
#36 | ACCEPTED | 0.34 s | details |
#37 | ACCEPTED | 0.34 s | details |
#38 | ACCEPTED | 0.35 s | details |
#39 | ACCEPTED | 0.34 s | details |
#40 | ACCEPTED | 0.34 s | details |
Compiler report
input/code.cpp: In function 'void cc(int)': input/code.cpp:15:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=0; i<rt[c].size(); ++i){ ^ input/code.cpp: In function 'void cy(int)': input/code.cpp:26:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=0; i<rt[c].size(); ++i){ ^ input/code.cpp: In function 'long long int gets(int, int)': input/code.cpp:39:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=0; i<rt[c].size(); ++i){ ^ input/code.cpp:51:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i=1; i<getsv.size(); ++i){ ^
Code
#include <iostream> #include <vector> using namespace std; int n; vector<int> rt[4040]; int aid[4040][4040]; int yid[4040][4040]; int u[4040]; void cc(int c){ aid[c][0]=1; for (int i=0; i<rt[c].size(); ++i){ int w=rt[c][i]; if (u[c]==w) continue; u[w]=c; cc(w); ++aid[c][1]; for (int i=1; i<4040; ++i) aid[c][i+1]+=aid[w][i]; } } void cy(int c){ for (int i=0; i<rt[c].size(); ++i){ int w=rt[c][i]; if (u[c]==w) continue; yid[w][1]=1; for (int i=1; i<4040; ++i) yid[w][i+1]+=(aid[c][i]+yid[c][i]-aid[w][i-1]); cy(w); } } vector<long long> getsv; long long dp[4040][4]; long long gets(int c, int d){ getsv.clear(); for (int i=0; i<rt[c].size(); ++i){ int w=rt[c][i]; if (w==u[c]) continue; if (aid[w][d-1]) getsv.push_back(aid[w][d-1]); } if (yid[c][d]) getsv.push_back(yid[c][d]); if (getsv.size()<3) return 0; // cout << "getsv: "; // for (int i=0; i<getsv.size(); ++i) cout << getsv[i] << " "; // cout << endl; dp[0][0]=1; dp[0][1]=getsv[0]; for (int i=1; i<getsv.size(); ++i){ dp[i][0]=1; dp[i][1]=dp[i-1][1]+getsv[i]; dp[i][2]=dp[i-1][2]+dp[i-1][1]*getsv[i]; dp[i][3]=dp[i-1][3]+dp[i-1][2]*getsv[i]; } // cout << "gets(" << c << ", " << d << ")=" << dp[getsv.size()-1][3] << "\n"; return dp[getsv.size()-1][3]; } int main(){ cin >> n; for (int i=1; i<n; ++i){ int a, b; cin >> a >> b; rt[a].push_back(b); rt[b].push_back(a); } cc(1); cy(1); for (int d=1; d<n; ++d){ // cout << "d-nice-d: " << d << endl; long long ans=0; if (d%2==0){ for (int i=1; i<=n; ++i){ ans+=gets(i, d/2); } } cout << ans << " "; }cout << "\n"; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
694 141 214 214 505 141 339 339 180 ... |
correct output |
---|
0 1301 0 12977 0 76694 0 21315... |
user output |
---|
0 1301 0 12977 0 76694 0 21315... |
Test 2
Verdict: ACCEPTED
input |
---|
928 534 15 15 364 364 66 364 726 ... |
correct output |
---|
0 1852 0 23152 0 157299 0 4823... |
user output |
---|
0 1852 0 23152 0 157299 0 4823... |
Test 3
Verdict: ACCEPTED
input |
---|
2925 2093 1182 2093 2577 1182 2213 2213 1630 ... |
correct output |
---|
0 5201 0 61916 0 512021 0 2340... |
user output |
---|
0 5201 0 61916 0 512021 0 2340... |
Test 4
Verdict: ACCEPTED
input |
---|
3198 660 2400 660 2620 2620 3008 2400 179 ... |
correct output |
---|
0 6434 0 102245 0 1122654 0 46... |
user output |
---|
0 6434 0 102245 0 1122654 0 46... |
Test 5
Verdict: ACCEPTED
input |
---|
869 142 549 142 335 142 684 549 409 ... |
correct output |
---|
0 1604 0 11624 0 56768 0 17500... |
user output |
---|
0 1604 0 11624 0 56768 0 17500... |
Test 6
Verdict: ACCEPTED
input |
---|
1514 904 557 557 957 957 754 904 250 ... |
correct output |
---|
0 3202 0 33876 0 243297 0 9322... |
user output |
---|
0 3202 0 33876 0 243297 0 9322... |
Test 7
Verdict: ACCEPTED
input |
---|
2133 1166 813 1166 751 813 416 1166 1743 ... |
correct output |
---|
0 4720 0 75657 0 705952 0 2953... |
user output |
---|
0 4720 0 75657 0 705952 0 2953... |
Test 8
Verdict: ACCEPTED
input |
---|
1833 1368 837 837 1296 1296 481 1296 548 ... |
correct output |
---|
0 3365 0 44752 0 313240 0 1147... |
user output |
---|
0 3365 0 44752 0 313240 0 1147... |
Test 9
Verdict: ACCEPTED
input |
---|
3446 3060 2907 2907 1089 1089 3155 3060 444 ... |
correct output |
---|
0 7068 0 80352 0 602995 0 3052... |
user output |
---|
0 7068 0 80352 0 602995 0 3052... |
Test 10
Verdict: ACCEPTED
input |
---|
55 28 23 23 43 43 41 28 48 ... |
correct output |
---|
0 70 0 262 0 97 0 35 0 12 0 0 ... |
user output |
---|
0 70 0 262 0 97 0 35 0 12 0 0 ... |
Test 11
Verdict: ACCEPTED
input |
---|
4000 3717 1739 3717 2875 3717 598 2875 3860 ... |
correct output |
---|
0 8708 0 147350 0 1310042 0 60... |
user output |
---|
0 8708 0 147350 0 1310042 0 60... |
Test 12
Verdict: ACCEPTED
input |
---|
4000 2607 3595 2607 3401 3401 1971 3401 3641 ... |
correct output |
---|
0 7518 0 95122 0 775490 0 4259... |
user output |
---|
0 7518 0 95122 0 775490 0 4259... |
Test 13
Verdict: ACCEPTED
input |
---|
4000 337 3391 337 783 337 721 337 2376 ... |
correct output |
---|
0 7128 0 86950 0 781051 0 4647... |
user output |
---|
0 7128 0 86950 0 781051 0 4647... |
Test 14
Verdict: ACCEPTED
input |
---|
4000 740 1571 740 1104 1104 2145 2145 3441 ... |
correct output |
---|
0 8699 0 169586 0 2358841 0 13... |
user output |
---|
0 8699 0 169586 0 2358841 0 13... |
Test 15
Verdict: ACCEPTED
input |
---|
4000 878 154 878 2194 2194 2037 2194 893 ... |
correct output |
---|
0 7747 0 101093 0 954212 0 646... |
user output |
---|
0 7747 0 101093 0 954212 0 646... |
Test 16
Verdict: ACCEPTED
input |
---|
4000 1739 685 1739 424 1739 743 1739 2656 ... |
correct output |
---|
0 10650673999 0 0 0 0 0 0 0 0 ... |
user output |
---|
0 10650673999 0 0 0 0 0 0 0 0 ... |
Test 17
Verdict: ACCEPTED
input |
---|
4000 2508 3693 2508 2165 2508 1689 3693 1935 ... |
correct output |
---|
0 1337338368 0 184329476 0 198... |
user output |
---|
0 1337338368 0 184329476 0 198... |
Test 18
Verdict: ACCEPTED
input |
---|
4000 813 3566 813 2763 813 1541 813 1762 ... |
correct output |
---|
0 426275345 0 2043667310 0 0 0... |
user output |
---|
0 426275345 0 2043667310 0 0 0... |
Test 19
Verdict: ACCEPTED
input |
---|
4000 725 282 725 365 725 3660 282 3202 ... |
correct output |
---|
0 666208836 0 972188838 0 0 0 ... |
user output |
---|
0 666208836 0 972188838 0 0 0 ... |
Test 20
Verdict: ACCEPTED
input |
---|
4000 1579 3029 1579 891 3029 2534 891 257 ... |
correct output |
---|
0 1184481790 0 0 0 0 0 0 0 0 0... |
user output |
---|
0 1184481790 0 0 0 0 0 0 0 0 0... |
Test 21
Verdict: ACCEPTED
input |
---|
4000 1996 520 1996 1978 1996 2196 1978 2182 ... |
correct output |
---|
0 1184359951 0 2360565396 0 0 ... |
user output |
---|
0 1184359951 0 2360565396 0 0 ... |
Test 22
Verdict: ACCEPTED
input |
---|
4000 1518 2792 1518 1956 1518 1572 2792 3898 ... |
correct output |
---|
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ... |
user output |
---|
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ... |
Test 23
Verdict: ACCEPTED
input |
---|
4000 2266 1993 2266 2140 2266 2230 2266 866 ... |
correct output |
---|
0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 ... |
user output |
---|
0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 ... |
Test 24
Verdict: ACCEPTED
input |
---|
4000 3923 1832 3923 1341 3923 856 3923 1130 ... |
correct output |
---|
0 10 0 10 0 10 0 10 0 10 0 10 ... |
user output |
---|
0 10 0 10 0 10 0 10 0 10 0 10 ... |
Test 25
Verdict: ACCEPTED
input |
---|
4000 103 2255 103 24 103 2124 103 535 ... |
correct output |
---|
0 1556 0 39 0 1 0 0 0 0 0 0 0 ... |
user output |
---|
0 1556 0 39 0 1 0 0 0 0 0 0 0 ... |
Test 26
Verdict: ACCEPTED
input |
---|
4000 1271 1635 1271 3388 1271 3452 1271 3371 ... |
correct output |
---|
0 2780 0 32 0 0 0 0 0 0 0 0 0 ... |
user output |
---|
0 2780 0 32 0 0 0 0 0 0 0 0 0 ... |
Test 27
Verdict: ACCEPTED
input |
---|
4000 257 1671 257 2439 257 756 257 1393 ... |
correct output |
---|
0 1406 0 56 0 4 0 0 0 0 0 0 0 ... |
user output |
---|
0 1406 0 56 0 4 0 0 0 0 0 0 0 ... |
Test 28
Verdict: ACCEPTED
input |
---|
4000 3694 1140 3694 1224 3694 1601 3694 3050 ... |
correct output |
---|
0 1570 0 83 0 15 0 2 0 0 0 0 0... |
user output |
---|
0 1570 0 83 0 15 0 2 0 0 0 0 0... |
Test 29
Verdict: ACCEPTED
input |
---|
4000 1449 2360 1449 611 1449 2332 1449 830 ... |
correct output |
---|
0 2504 0 43 0 1 0 0 0 0 0 0 0 ... |
user output |
---|
0 2504 0 43 0 1 0 0 0 0 0 0 0 ... |
Test 30
Verdict: ACCEPTED
input |
---|
4000 2519 595 2519 1119 2519 500 2519 2127 ... |
correct output |
---|
0 2250 0 54 0 0 0 0 0 0 0 0 0 ... |
user output |
---|
0 2250 0 54 0 0 0 0 0 0 0 0 0 ... |
Test 31
Verdict: ACCEPTED
input |
---|
4000 2787 2780 2787 3471 2787 206 2787 2050 ... |
correct output |
---|
0 1565 0 90 0 1 0 0 0 0 0 0 0 ... |
user output |
---|
0 1565 0 90 0 1 0 0 0 0 0 0 0 ... |
Test 32
Verdict: ACCEPTED
input |
---|
4000 1977 2196 1977 1810 1977 128 1977 436 ... |
correct output |
---|
0 1536 0 67 0 6 0 0 0 0 0 0 0 ... |
user output |
---|
0 1536 0 67 0 6 0 0 0 0 0 0 0 ... |
Test 33
Verdict: ACCEPTED
input |
---|
4000 3377 1793 3377 2977 3377 711 3377 2184 ... |
correct output |
---|
0 2524 0 36 0 3 0 0 0 0 0 0 0 ... |
user output |
---|
0 2524 0 36 0 3 0 0 0 0 0 0 0 ... |
Test 34
Verdict: ACCEPTED
input |
---|
4000 3617 2852 3617 3552 3617 2064 3617 88 ... |
correct output |
---|
0 2492 0 37 0 0 0 0 0 0 0 0 0 ... |
user output |
---|
0 2492 0 37 0 0 0 0 0 0 0 0 0 ... |
Test 35
Verdict: ACCEPTED
input |
---|
4000 2713 1183 2713 565 2713 1432 2713 2859 ... |
correct output |
---|
0 1370 0 99 0 4 0 38 0 0 0 0 0... |
user output |
---|
0 1370 0 99 0 4 0 38 0 0 0 0 0... |
Test 36
Verdict: ACCEPTED
input |
---|
4000 3350 3568 3350 968 3350 3110 3350 149 ... |
correct output |
---|
0 2026 0 49 0 45 0 12 0 0 0 0 ... |
user output |
---|
0 2026 0 49 0 45 0 12 0 0 0 0 ... |
Test 37
Verdict: ACCEPTED
input |
---|
4000 1794 1797 1794 355 1794 728 1794 2107 ... |
correct output |
---|
0 2240 0 53 0 1 0 0 0 0 0 0 0 ... |
user output |
---|
0 2240 0 53 0 1 0 0 0 0 0 0 0 ... |
Test 38
Verdict: ACCEPTED
input |
---|
4000 1571 2107 1571 1258 1571 1808 1571 1754 ... |
correct output |
---|
0 1765 0 51 0 4 0 0 0 0 0 0 0 ... |
user output |
---|
0 1765 0 51 0 4 0 0 0 0 0 0 0 ... |
Test 39
Verdict: ACCEPTED
input |
---|
4000 2132 1514 2132 3357 2132 355 2132 3958 ... |
correct output |
---|
0 1991 0 34 0 12 0 0 0 0 0 0 0... |
user output |
---|
0 1991 0 34 0 12 0 0 0 0 0 0 0... |
Test 40
Verdict: ACCEPTED
input |
---|
4000 1621 743 1621 1182 1621 1598 1621 2693 ... |
correct output |
---|
0 2500 0 22 0 2 0 0 0 0 0 0 0 ... |
user output |
---|
0 2500 0 22 0 2 0 0 0 0 0 0 0 ... |