QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #507194 | #6312. 城市建造 | kymmykym# | 0 | 71ms | 11848kb | C++14 | 1.8kb | 2024-08-06 13:11:08 | 2024-08-06 13:11:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100005;
const int MOD=998244353;
int n,m,k;
bool vis[maxn];
vector<int>adj[maxn];
int ans;
int sz[maxn];
void pre(int x, int p){
sz[x]=1;
vector<int>childs;
for(auto v:adj[x]){
if(v!=p){
pre(v,x);
sz[x]+=sz[v];
childs.push_back(sz[v]);
}
}
childs.push_back(n-sz[x]);
sort(childs.begin(),childs.end());
childs[0]++;
sort(childs.begin(),childs.end());
int diff=abs(childs.back()-childs[0]);
if(childs[0] >= 2 && childs.size() > 1 && diff<=k)++ans;
}
int memo[maxn][2];
int dpdp(int x, bool done, int p){
if(~memo[x][done])return memo[x][done];
if(done && adj[x].size() > 1){//literally cannot connect to childs.
return 0;
}
if(done){
return 1;
}
if(adj[x].size() == 1){
return 1;
}
vector<int>childs;
int res=0;
int c1=1;
for(auto v:adj[x])if(v!=p){
childs.push_back(v);
c1=(c1*dpdp(v,0,x))%MOD;
}
res=c1;
int S=adj[x].size();
int pre[S+3],suf[S+3];
for(int i=0;i<childs.size();i++){
if(i)pre[i]=pre[i-1]*dpdp(childs[i],0,x)%MOD;
else pre[i]=dpdp(childs[i],0,x);
}
for(int i=(int)childs.size()-1;i>=0;i--){
if(i!=(int)childs.size()-1)suf[i]=suf[i+1]*dpdp(childs[i],0,x)%MOD;
else suf[i]=dpdp(childs[i],0,x);
}
for(int i=0;i<(int)childs.size();i++){
int ways=1;
if(i>0)ways=pre[i-1];
if(i<(int)childs.size()-1)ways=ways*suf[i+1]%MOD;
ways=ways*dpdp(childs[i],1,x)%MOD;
res=(res+ways)%MOD;
}
return memo[x][done]=res;
}
int32_t main(){
cin >> n >> m >> k;
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int rt=1;
for(int i=1;i<=n;i++){
if(adj[i].size()!=1)rt=i;
}
ans=0;
pre(rt,-1);
memset(memo,-1,sizeof memo);
cout<<(ans+dpdp(rt,0,-1))%MOD;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 0
Memory Limit Exceeded
input:
15 20 0 2 7 14 7 11 12 15 9 6 2 11 4 5 10 15 7 8 4 12 5 10 1 14 4 6 8 8 15 7 14 10 14 2 6 13 10 7 13 8 3
output:
result:
Test #2:
score: 0
Memory Limit Exceeded
input:
15 20 0 1 14 5 12 6 1 5 12 9 2 11 10 6 9 11 7 15 3 1 10 8 1 10 15 13 8 3 11 15 11 1 2 8 12 13 4 10 11 4 5
output:
result:
Test #3:
score: 0
Memory Limit Exceeded
input:
20 50 1 11 19 16 2 5 1 15 2 14 16 16 14 16 20 6 7 8 7 19 15 8 7 20 12 14 18 2 15 15 19 4 3 1 8 16 12 18 14 3 9 7 8 13 2 9 17 15 11 4 10 12 20 7 8 8 7 7 8 4 3 8 6 6 8 15 19 2 13 9 17 3 16 8 1 7 8 3 9 3 10 5 1 8 1 5 1 5 1 13 2 7 6 15 19 3 8 3 4 4 10
output:
result:
Test #4:
score: 0
Memory Limit Exceeded
input:
20 50 1 14 9 20 10 6 19 20 4 11 19 12 2 20 4 14 9 17 9 3 7 9 13 2 3 3 7 19 13 8 15 11 13 14 1 9 5 17 10 9 16 2 12 6 13 2 12 10 17 8 15 18 14 13 6 6 13 9 17 3 7 17 7 6 19 8 7 14 18 9 5 11 13 11 13 2 3 19 13 7 17 9 16 8 7 13 9 11 6 7 8 17 4 5 16 9 17 11 13 7 15
output:
result:
Test #5:
score: 0
Memory Limit Exceeded
input:
20 50 1 8 17 19 7 19 12 13 3 17 11 13 11 19 7 2 12 17 7 12 7 18 14 9 14 18 16 7 13 8 1 11 13 3 13 12 7 9 16 17 13 3 15 16 9 4 15 11 10 7 17 18 14 20 1 15 13 18 9 11 7 10 6 20 1 17 20 14 16 13 16 20 1 3 15 10 6 1 8 13 16 13 17 16 9 6 10 7 19 12 2 5 6 1 17 15 4 16 7 7 17
output:
result:
Test #6:
score: 0
Memory Limit Exceeded
input:
200 300 0 35 199 36 155 149 132 176 127 49 2 193 70 103 56 148 152 38 128 2 37 148 7 122 67 19 134 103 19 76 118 52 54 159 51 130 122 107 196 63 172 71 42 174 33 66 170 51 100 102 92 53 106 77 135 103 134 9 52 164 140 185 13 116 138 6 70 69 178 198 23 146 74 87 101 68 194 144 69 105 163 71 78 56 65 ...
output:
result:
Test #7:
score: 0
Memory Limit Exceeded
input:
200 300 0 73 128 63 135 186 29 47 95 68 164 145 2 112 171 190 83 82 186 191 124 29 14 104 75 58 133 135 63 39 136 143 181 105 182 174 150 17 193 84 9 143 102 67 182 12 124 99 179 28 107 198 188 63 26 91 94 135 63 54 74 137 150 84 199 18 135 156 88 34 13 200 157 114 156 196 118 81 116 23 10 197 169 1...
output:
result:
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 8524kb
input:
2000 1999 1 465 582 845 1459 282 1900 537 152 150 257 1108 710 1144 1451 1262 815 1566 1262 761 439 1265 198 1419 15 480 294 1054 1251 234 367 850 90 344 67 1229 180 1454 1844 1323 1008 1982 348 96 1282 585 919 939 1210 360 437 807 1 757 1533 425 238 138 685 1808 1066 1683 1001 1566 569 1184 1737 11...
output:
116891212
result:
wrong answer 1st numbers differ - expected: '116891230', found: '116891212'
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 7968kb
input:
2000 1999 1 540 1725 1919 242 627 762 695 1264 1377 1351 309 1749 1596 1297 983 1053 260 949 1218 1403 1144 1066 478 1515 1834 688 1525 480 1660 51 374 1207 878 335 833 217 1347 1429 1093 1477 1597 691 803 1081 1059 729 1225 1948 398 1071 1266 1578 1138 631 409 466 1105 1889 57 408 1356 123 1164 104...
output:
715143399
result:
wrong answer 1st numbers differ - expected: '715143401', found: '715143399'
Test #10:
score: 0
Memory Limit Exceeded
input:
2000 3000 0 1642 694 947 9 706 385 1 1618 1844 402 442 309 1802 734 333 197 1194 1204 373 1123 891 1281 1907 449 1093 1612 1316 1178 1407 841 708 279 1542 1703 885 1900 1658 971 1493 1908 1299 485 1510 1050 644 958 414 1187 869 1250 1167 495 966 1935 932 468 1769 1260 1040 804 549 1487 620 775 1857 ...
output:
result:
Test #11:
score: 0
Memory Limit Exceeded
input:
2000 3000 0 408 1484 1521 1118 1045 1938 1090 1897 1432 529 647 1015 1320 1655 1909 1873 1323 989 478 1778 1934 1145 963 1949 871 1716 829 1605 139 860 1757 232 45 1321 1197 627 1634 1366 47 1576 691 1413 1920 252 1366 419 1431 525 439 842 22 1848 536 1479 350 334 663 1412 170 1666 749 1794 149 957 ...
output:
result:
Test #12:
score: 0
Memory Limit Exceeded
input:
2000 3000 1 1042 636 1347 1373 16 1538 405 377 1353 1413 139 221 1448 26 797 822 811 880 1380 976 1999 144 1392 1240 1161 886 1740 817 460 263 1519 926 1491 1776 660 1177 1143 702 1377 1526 771 784 893 536 1725 1581 623 584 960 9 1744 1680 1399 351 1975 1290 177 832 1465 1858 541 310 15 369 208 600 ...
output:
result:
Test #13:
score: 0
Memory Limit Exceeded
input:
2000 3000 1 399 842 1957 1476 1284 1494 109 1498 1714 1156 533 1573 59 884 1961 1142 600 1179 1557 1380 1468 1541 396 1343 252 629 914 1408 1867 1793 770 1459 1797 1870 1696 282 541 869 1173 1065 980 991 289 1995 765 1343 628 1487 1229 111 555 686 1142 1309 642 1731 809 1498 1828 1134 1954 1151 1768...
output:
result:
Test #14:
score: 0
Wrong Answer
time: 71ms
memory: 11848kb
input:
100000 99999 1 51817 26399 15817 96313 49906 51230 78680 242 31802 66868 30357 78985 12525 6836 21594 17217 51918 70113 34779 36388 39346 27341 23790 83913 67772 74306 79030 8675 13297 48602 31050 35041 88425 8465 2567 50848 32581 25543 17562 66633 50079 89402 21395 31562 82946 75355 36292 48542 178...
output:
213549478
result:
wrong answer 1st numbers differ - expected: '213549735', found: '213549478'
Test #15:
score: 0
Wrong Answer
time: 63ms
memory: 11848kb
input:
100000 99999 1 36876 91 57635 85878 73848 6445 56560 31152 92050 83033 84343 84735 19344 59385 16031 82742 24733 35911 28824 52694 89526 7696 47243 72123 7605 41706 40153 16549 117 72375 94514 57348 31759 46680 31370 59666 4180 17810 8025 44622 21906 56373 33740 12923 25841 43798 45198 88125 99159 9...
output:
219797332
result:
wrong answer 1st numbers differ - expected: '697917401', found: '219797332'
Test #16:
score: 0
Memory Limit Exceeded
input:
100000 200000 0 73311 26692 47112 50996 80957 18065 55469 44726 18171 14114 1652 41393 33535 58668 10619 90228 62378 80677 78580 22495 20629 89185 98877 21979 36123 37841 20762 58459 28399 29048 94059 29696 88568 84814 57216 16617 48405 54760 1772 58208 78839 23779 56785 90360 71929 74555 89985 4599...
output:
result:
Test #17:
score: 0
Memory Limit Exceeded
input:
100000 200000 0 74724 58001 2096 36434 10780 66175 8075 91461 98543 76912 91080 58166 91369 63734 86609 37092 76236 17518 27092 86029 49327 96255 55749 32047 59513 4477 21883 24851 12313 11034 58127 78948 38744 21465 52775 15415 26264 19640 80625 57520 96868 34807 46432 91667 34092 71798 48442 53707...
output:
result:
Test #18:
score: 0
Memory Limit Exceeded
input:
100000 200000 1 41399 84309 59315 57604 76994 41146 89914 5576 10071 2828 40663 32009 8115 72560 15544 30127 75408 15716 13752 40186 49595 42893 93363 66913 35917 59205 4350 58352 84832 39487 93821 1026 52401 33617 90465 3287 16829 33543 86825 73171 69299 16118 35588 53961 58170 44730 50174 71526 44...
output:
result:
Test #19:
score: 0
Memory Limit Exceeded
input:
100000 200000 1 61682 10243 91643 23294 5766 66088 44830 3952 93132 17701 5776 2236 76832 71195 38033 22975 40375 14419 97543 53348 62755 10220 47663 55955 40946 33673 56759 68401 88580 110 62264 25662 214 77675 36373 6940 28023 41926 81352 23162 72657 86572 25487 97838 70762 3628 23027 37780 36529 ...
output:
result:
Test #20:
score: 0
Memory Limit Exceeded
input:
100000 200000 1 83161 92368 783 10781 95621 57345 93279 74412 96084 29764 83839 59585 68295 38546 18951 68761 30461 32813 95888 94000 71796 53643 24398 22834 85633 84908 37566 53874 35140 67126 24519 82526 97616 83915 65640 11899 53812 97833 44761 28536 65548 37212 91762 5827 73676 56073 46769 95173...