QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #167124 | #2991. 秘密袭击 | Cidoai# | 0 | 0ms | 0kb | C++14 | 1.8kb | 2023-09-07 09:32:02 | 2023-09-07 09:32:03 |
answer
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
inline int read(){
int x=0;
int f=0,ch=0;
while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
return f?-x:x;
}
inline void write(int x,char end=' '){
if(x==0){
putchar('0');
putchar(end);
return;
}
if(x<0) putchar('-'),x=-x;
int ch[70]={0},cnt=0;
while(x){
ch[cnt++]=(int)(x%10);
x/=10;
}
while(cnt--) putchar(ch[cnt]+48);
putchar(end);
}
const ll mod=64123;
const int N=2005;
int n,k,w;
int d[N],fa[N];
struct node{
int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int du[N];
ll ans;
inline void dfs1(int u){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa[u]) continue;
fa[v]=u;
dfs1(v);
}
}
vector<int> vec;
int sz;
inline void ins(int x){
if(sz==0){
vec.push_back(x),++sz;
return;
}
int l=0,r=sz;
while(l<r){
int mid=(l+r)>>1;
if(vec[mid]<x) r=mid;
else l=mid+1;
}
vec.insert(vec.begin()+l,x);
++sz;
}
inline void del(int x){
int l=0,r=sz;
while(l<r){
int mid=(l+r)>>1;
if(vec[mid]<=x) r=mid;
else l=mid+1;
}
vec.erase(vec.begin()+l);
--sz;
}
inline void dfs2(int u){
ins(d[u]);
if(sz>=k) ans=(ans+vec[k-1])%mod;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa[u]) continue;
dfs2(v);
}
del(d[u]);
}
int main(){
freopen("coat.in","r",stdin);
freopen("coat.out","w",stdout);
n=read(),k=read(),w=read();
for(int i=1;i<=n;++i) d[i]=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
add(u,v);
add(v,u);
du[u]++,du[v]++;
}
int rt=0;
for(int i=1;i<=n;++i){
if(du[i]==1){
rt=i;
break;
}
}
dfs1(rt);
for(int i=1;i<=n;++i) dfs2(i);
write(ans%mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
3 3 1666 243 416 1486 1 2 3 2
output:
result:
Test #2:
score: 0
Dangerous Syscalls
input:
15 14 1666 640 1439 1195 875 1642 936 1116 376 982 940 494 1567 522 901 1461 10 14 8 7 9 12 2 4 1 2 9 7 11 8 10 8 3 2 15 4 6 5 5 4 13 9 7 6
output:
result:
Test #3:
score: 0
Dangerous Syscalls
input:
20 20 1666 1469 1570 1074 1435 339 1156 285 456 429 1382 1334 191 221 1607 930 1289 1204 788 245 1424 16 15 6 3 2 1 14 13 17 18 12 15 9 10 5 4 5 12 13 12 4 3 8 3 19 18 2 3 4 11 4 9 16 17 4 7 19 20
output:
result:
Test #4:
score: 0
Dangerous Syscalls
input:
300 272 10 2 2 8 5 9 9 4 7 2 9 9 10 4 6 4 10 8 7 5 9 10 10 5 2 3 1 2 6 6 1 3 2 6 6 2 4 5 7 7 6 3 8 4 8 2 8 6 4 3 1 7 10 2 4 5 10 7 10 4 5 3 6 2 3 9 4 5 3 5 2 2 10 3 6 4 2 7 9 5 2 8 5 1 2 2 2 2 3 6 4 1 6 2 7 5 7 10 1 7 8 5 3 1 4 5 9 4 6 5 4 5 6 7 5 5 3 6 5 7 2 3 8 4 5 10 7 8 10 9 10 4 10 9 6 10 10 2 ...
output:
result:
Test #5:
score: 0
Dangerous Syscalls
input:
1666 1630 1666 985 1476 1136 521 707 874 363 1417 2 694 1345 1463 578 523 339 1617 1218 1408 645 1208 1224 1332 684 191 1239 813 1616 1439 694 1536 59 141 1343 1056 149 374 100 652 1221 1252 344 453 662 1464 1232 716 140 827 393 1167 1530 1226 484 938 1586 595 711 831 1000 863 890 1540 35 189 740 14...
output:
result:
Test #6:
score: 0
Dangerous Syscalls
input:
50 46 1666 1566 976 171 398 574 378 1356 1245 1371 158 1045 1347 1064 454 1223 456 1188 1428 1253 436 978 1278 1592 748 883 378 1650 1225 121 1201 517 1522 1561 857 659 277 451 616 1198 370 481 597 996 1465 1298 690 1513 883 945 704 35 34 11 9 1 2 15 16 6 5 25 22 30 27 32 36 22 19 5 2 39 36 8 10 42 ...
output:
result:
Test #7:
score: 0
Dangerous Syscalls
input:
200 178 1666 1142 1649 112 634 1132 245 1075 178 1182 1070 755 165 1405 1177 1572 93 1611 1206 265 1288 117 260 23 30 182 1067 879 6 1171 1414 1192 906 697 1234 295 573 588 1306 1038 435 94 1456 365 1524 277 1527 1300 1577 1068 335 914 346 1381 672 511 1527 385 986 314 243 73 550 902 706 335 1324 12...
output:
result:
Test #8:
score: 0
Dangerous Syscalls
input:
500 461 1666 1432 303 1066 1022 1046 978 33 306 543 1554 169 1055 1193 1043 1120 343 289 826 816 1367 778 913 403 477 1183 1473 557 1568 781 938 475 384 428 71 889 215 1150 828 850 1538 899 692 1495 120 1516 1269 214 164 1555 1655 283 761 944 231 436 829 326 1640 266 719 1435 446 466 1382 123 1368 1...
output:
result:
Test #9:
score: 0
Dangerous Syscalls
input:
1111 100 100 35 75 32 20 5 51 92 68 28 27 93 52 62 54 70 33 41 31 14 36 96 52 21 33 56 91 63 89 30 98 66 7 41 46 68 89 74 31 2 47 81 1 39 7 31 53 11 23 55 24 11 41 22 41 47 81 52 85 62 89 46 40 26 56 13 21 16 61 55 84 19 90 27 60 45 82 86 70 45 82 67 36 27 66 18 26 10 21 35 75 90 18 57 52 100 24 78 ...
output:
result:
Test #10:
score: 0
Dangerous Syscalls
input:
1111 50 1111 178 191 358 143 796 130 1098 385 384 224 435 503 5 822 617 299 452 1034 409 52 197 707 426 488 621 720 513 999 317 561 336 427 590 575 998 401 150 433 70 414 777 784 1085 832 322 619 971 1022 563 210 282 230 27 548 683 481 905 654 943 351 511 268 125 166 345 426 440 426 851 1092 647 426...
output:
result:
Test #11:
score: 0
Dangerous Syscalls
input:
1111 100 1666 814 171 338 1058 500 1599 1294 1493 821 578 1652 852 1335 883 942 1557 1085 1110 1264 656 981 735 105 194 207 654 553 151 187 1508 1018 1313 519 1218 101 368 1462 1253 1573 1627 727 300 1639 1539 706 910 661 1264 861 391 549 1628 1587 1109 1040 655 1204 1275 919 378 1290 800 829 841 12...
output:
result:
Test #12:
score: 0
Dangerous Syscalls
input:
1666 100 1666 776 742 289 947 709 832 612 889 836 833 1413 1050 746 1519 1515 1117 291 321 49 14 1216 551 686 1073 501 782 1226 984 190 1266 1127 516 1306 654 471 760 366 409 466 1153 1558 76 1122 622 1050 1588 1186 1566 890 706 594 1366 362 317 634 751 1072 421 1335 870 639 353 532 1564 257 655 194...
output:
result:
Test #13:
score: 0
Dangerous Syscalls
input:
1666 200 1666 1254 1366 1102 777 1401 582 1082 473 545 716 435 190 917 12 194 809 1233 531 416 73 1469 1539 874 684 1367 725 484 1242 1220 84 900 1147 387 1027 716 297 1630 1646 1375 167 146 1492 568 8 127 1040 1517 148 324 514 935 1388 38 1047 370 839 1331 78 239 1092 33 63 842 630 1103 142 925 229...
output:
result:
Test #14:
score: 0
Dangerous Syscalls
input:
1666 500 1666 1529 651 1370 1618 415 185 1364 1420 65 678 981 1039 1406 972 1140 690 1282 1255 863 1067 579 1143 726 431 584 622 1286 361 639 1304 896 384 815 1642 1528 202 79 1294 208 1496 1260 794 1553 1388 1114 222 79 651 40 300 1212 1526 1585 798 783 1230 1167 1090 351 1597 974 544 1290 365 1109...
output:
result:
Test #15:
score: 0
Dangerous Syscalls
input:
1666 1486 1666 309 1241 559 606 930 1628 1440 1519 1346 642 181 710 712 293 1049 58 1574 1601 1129 1112 714 883 98 1635 1344 771 909 1137 12 188 356 617 1001 1234 185 277 656 1304 43 1624 331 37 310 1035 104 1652 718 1405 309 1182 37 1610 1473 599 23 891 718 940 40 753 934 540 246 749 151 1485 518 1...
output:
result:
Test #16:
score: 0
Dangerous Syscalls
input:
1666 1498 1666 1435 1328 1264 388 1474 960 496 1593 1294 1428 548 1151 1281 677 897 432 1314 692 1593 248 14 1556 356 1114 93 1057 556 1596 1082 760 934 1294 1250 729 144 717 314 122 122 671 1265 250 239 1628 1180 55 1142 1031 40 538 1542 657 1203 207 1577 967 740 1023 784 183 1316 1162 1481 880 102...
output:
result:
Test #17:
score: 0
Dangerous Syscalls
input:
1666 1630 1666 280 484 1346 426 673 1024 1368 1100 1284 81 1056 1127 426 1137 936 784 260 728 577 591 1334 1414 900 1492 581 838 966 732 579 611 488 1484 889 1145 11 708 418 392 1222 910 1659 699 25 99 1489 1562 536 594 1171 1110 1241 1094 992 1017 1382 108 1411 862 1627 1036 1578 215 275 354 1405 1...
output:
result:
Test #18:
score: 0
Dangerous Syscalls
input:
1666 1654 1666 401 945 1293 587 1220 1621 1208 290 1351 583 840 279 1253 1551 42 456 778 1382 554 31 475 451 809 343 1516 882 1550 839 212 312 500 1397 1443 716 1647 1417 1475 1030 715 775 772 1232 1603 1199 854 725 1305 129 1001 635 4 854 402 50 323 294 1157 773 1305 1201 1509 589 106 1251 1168 873...
output:
result:
Test #19:
score: 0
Dangerous Syscalls
input:
1666 1519 1666 66 1012 227 647 1526 26 12 1189 816 3 970 815 1172 77 412 1463 1555 412 273 952 190 88 962 562 1195 707 1496 447 221 235 1504 736 999 491 309 1420 1148 372 1039 182 1425 555 864 236 1313 288 1201 135 53 1539 826 710 655 928 155 37 228 764 164 1513 1042 574 953 1183 1635 1417 1030 26 6...
output:
result:
Test #20:
score: 0
Dangerous Syscalls
input:
1666 1613 1666 158 283 180 147 1191 425 1524 402 175 1146 1495 993 1618 1039 777 1609 623 901 887 1515 1598 741 1306 746 316 340 1019 940 1330 1260 695 425 410 1651 253 170 276 1329 1321 1561 1618 29 342 1274 1440 703 239 1177 899 1209 1614 1026 449 222 306 700 1074 1294 394 935 1260 952 1062 1239 1...