QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#302757 | #952. Spring cleaning | monster_hunter | 35 | 50ms | 18628kb | C++14 | 2.6kb | 2024-01-11 11:18:50 | 2024-01-11 11:18:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct edge{
LL to,nt;
}a[200005];
LL tree[100005];
LL num[100005],nxt[100005];
LL sum[100005];
LL dfn[100005],low[100005];
LL tmp[100005];
LL val[100005][2];
bool flag[100005];
LL deg[100005];
LL n,i,j,k,m,dfs_clock=0,sum1=0,ans=0,x,y,cnt=0;
LL root=0;
void add(LL x,LL y){
a[++cnt].to=y;a[cnt].nt=nxt[x];nxt[x]=cnt;
}
LL cmp(LL x,LL y){
return dfn[x]>dfn[y];
}
LL lowbit(LL x){
return x & -x;
}
void insert(LL x,LL val){
while(x<=n){
tree[x]+=val;
x+=lowbit(x);
}
}
LL query(LL x){
LL sum=0;
while(x){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
void dfs(LL father,LL x){
dfn[x]=++dfs_clock;
if(deg[x]==1) sum[x]=1;
for(LL i=nxt[x];i;i=a[i].nt)
if(a[i].to!=father){
dfs(x,a[i].to);
sum[x]+=sum[a[i].to];
}
low[x]=dfs_clock;
if(x!=root){
if(sum[x]%2==0){
ans+=2;
val[x][0]++;
}
else{
ans+=1;
val[x][1]++;
}
}
}
void dfs_getnum(LL father,LL x){
for(LL i=nxt[x];i;i=a[i].nt)
if(a[i].to!=father){
val[a[i].to][0]+=val[x][0];
val[a[i].to][1]+=val[x][1];
dfs_getnum(x,a[i].to);
}
}
int main() {
scanf("%lld%lld",&n,&m);
for(i=1;i<n;i++){
scanf("%lld%lld",&x,&y);
add(x,y);
add(y,x);
deg[x]++;deg[y]++;
}
for(i=1;i<=n;i++){
if(root==0 && deg[i]>1){
root=i;
}
else if(deg[i]==1) sum1++;
}
dfs(0,root);
dfs_getnum(0,root);
LL now=0;
LL cnt1=0;
for(i=1;i<=m;i++){
now=0;cnt1=0;
scanf("%lld",&tmp[0]);
for(j=1;j<=tmp[0];j++)
scanf("%lld",&tmp[j]);
sort(tmp+1,tmp+tmp[0]+1,cmp);
for(j=1;j<=tmp[0];j++){
if(deg[tmp[j]]==1){
if(flag[tmp[j]]==false){
now++;
flag[tmp[j]]=true;
}
else{
cnt1++;
LL num1=query(low[tmp[j]])-query(dfn[tmp[j]]-1);
if(num1%2==0){
now-=val[tmp[j]][0];
now+=val[tmp[j]][1];
}
else{
now+=val[tmp[j]][0];
now-=val[tmp[j]][1];
}
now++;
insert(dfn[tmp[j]],1);
}
}
else{
cnt1++;
LL num1=query(low[tmp[j]])-query(dfn[tmp[j]]-1);
if(num1%2==0){
now-=val[tmp[j]][0];
now+=val[tmp[j]][1];
}
else{
now+=val[tmp[j]][0];
now-=val[tmp[j]][1];
}
now++;
insert(dfn[tmp[j]],1);
}
}
if((sum1+cnt1)%2==1) printf("-1\n");
else printf("%lld\n",now+ans);
for(j=1;j<=tmp[0];j++){
if(deg[tmp[j]]==1){
if(flag[tmp[j]]==true) flag[tmp[j]]=false;
else insert(dfn[tmp[j]],-1);
}
else{
insert(dfn[tmp[j]],-1);
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
7 3 1 2 2 4 4 5 5 6 5 7 3 4 1 4 2 2 4 1 1
output:
-1 10 8
result:
ok 3 lines
Test #2:
score: -0
Wrong Answer
time: 18ms
memory: 10472kb
input:
20000 5000 9844 2753 14120 15267 6630 9346 16091 21 11589 11672 7243 10729 9376 18990 19172 16424 15329 4466 19473 2205 9722 13188 13805 12632 9639 7877 10960 12697 1725 10231 13383 4059 9258 10586 18536 11667 5581 666 1382 7072 17656 11359 10793 10158 18150 13161 9758 4811 280 4330 3962 17592 10138...
output:
23477 23464 23454 23468 23458 23455 23465 23445 23462 23459 23467 23458 23473 23459 23453 23464 23457 23466 23459 23462 23458 23454 23453 23453 23450 23460 23456 23460 23445 23456 23455 23462 23459 23449 23462 23470 23447 23462 23455 23459 23475 23459 23435 23458 23463 23443 23460 23461 23449 23460 ...
result:
wrong answer 1st lines differ - expected: '23481', found: '23477'
Subtask #2:
score: 9
Accepted
Test #3:
score: 9
Accepted
time: 8ms
memory: 9964kb
input:
3000 1 1 592 1 797 1 1542 1 1567 1 2784 1 455 1 140 1 2242 1 910 1 1018 1 961 1 661 1 2408 1 1791 1 776 1 2894 1 369 1 435 1 2441 1 519 1 2223 1 102 1 1478 1 2261 1 1920 1 2541 1 1835 1 1918 1 848 1 25 1 1993 1 1020 1 2852 1 719 1 226 1 2 1 156 1 13 1 748 1 2521 1 1762 1 2164 1 2905 1 2949 1 2994 1 ...
output:
84526
result:
ok single line: '84526'
Test #4:
score: 0
Accepted
time: 12ms
memory: 7844kb
input:
3000 1 1 2019 1 111 1 1364 1 1771 1 2378 1 2159 1 573 1 207 1 2070 1 620 1 888 1 335 1 2837 1 1317 1 221 1 2000 1 2633 1 1302 1 644 1 472 1 1874 1 1882 1 1309 1 2781 1 2213 1 2904 1 1085 1 389 1 2838 1 91 1 1107 1 1086 1 1627 1 949 1 1394 1 883 1 2744 1 2385 1 2298 1 799 1 2313 1 315 1 498 1 2873 1 ...
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 15ms
memory: 13732kb
input:
100000 1 1 54145 1 79089 1 74333 1 80683 1 71589 1 36284 1 36065 1 23877 1 52252 1 79993 1 54257 1 38347 1 33461 1 80038 1 69156 1 67331 1 35581 1 91618 1 5993 1 38827 1 37059 1 50347 1 65914 1 64402 1 56981 1 32705 1 73315 1 11098 1 61719 1 12911 1 37000 1 57320 1 80865 1 39114 1 56767 1 62511 1 41...
output:
105104
result:
ok single line: '105104'
Test #6:
score: 0
Accepted
time: 18ms
memory: 11760kb
input:
70000 1 1 56319 1 32897 1 69246 1 59111 1 5845 1 44069 1 44563 1 19533 1 31995 1 22157 1 13502 1 1307 1 42537 1 60784 1 40363 1 31983 1 23071 1 11304 1 48416 1 57872 1 13827 1 29632 1 60886 1 12738 1 59496 1 29988 1 7876 1 15279 1 26569 1 62592 1 22819 1 8963 1 7119 1 61345 1 37243 1 449 1 28767 1 5...
output:
178192
result:
ok single line: '178192'
Test #7:
score: 0
Accepted
time: 27ms
memory: 14888kb
input:
100000 1 1 52670 1 51157 1 66285 1 71477 1 43626 1 30699 1 4723 1 27122 1 21210 1 4707 1 58285 1 25305 1 55346 1 61958 1 60032 1 11283 1 65277 1 91648 1 79039 1 6055 1 18033 1 56975 1 52220 1 24114 1 97939 1 64658 1 13743 1 19269 1 77333 1 66756 1 64395 1 34692 1 72311 1 58534 1 27471 1 35410 1 6411...
output:
207612
result:
ok single line: '207612'
Subtask #3:
score: 9
Accepted
Test #8:
score: 9
Accepted
time: 8ms
memory: 8240kb
input:
5000 1 1342 1343 4110 4111 1415 1416 2960 2961 504 505 2756 2757 4496 4497 4178 4179 1933 1934 661 662 2894 2895 4041 4042 286 287 4881 4882 2988 2989 281 282 3038 3039 782 783 3878 3879 4914 4915 4578 4579 3877 3878 1870 1871 3014 3015 411 412 2711 2712 1479 1480 4818 4819 1930 1931 733 734 290 291...
output:
87526
result:
ok single line: '87526'
Test #9:
score: 0
Accepted
time: 12ms
memory: 10124kb
input:
5000 1 4605 4606 4467 4468 236 237 804 805 44 45 3706 3707 3222 3223 1600 1601 3132 3133 3201 3202 83 84 4075 4076 2487 2488 4100 4101 2709 2710 1564 1565 730 731 3934 3935 2859 2860 3382 3383 1490 1491 2915 2916 2921 2922 4292 4293 2149 2150 4866 4867 3894 3895 1499 1500 4826 4827 1389 1390 2565 25...
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 23ms
memory: 18628kb
input:
99000 1 79771 79772 79219 79220 95025 95026 74528 74529 74958 74959 60316 60317 89522 89523 50423 50424 18943 18944 95708 95709 85436 85437 89245 89246 88864 88865 45298 45299 80243 80244 45568 45569 86109 86110 88381 88382 40781 40782 80453 80454 74733 74734 83094 83095 38257 38258 87260 87261 9654...
output:
150655
result:
ok single line: '150655'
Test #11:
score: 0
Accepted
time: 31ms
memory: 17396kb
input:
90000 1 82770 82771 86846 86847 57191 57192 2404 2405 72238 72239 38989 38990 4520 4521 85621 85622 38425 38426 88887 88888 84483 84484 84979 84980 55756 55757 81666 81667 84172 84173 84048 84049 86248 86249 35519 35520 34092 34093 26006 26007 37509 37510 46515 46516 50285 50286 28067 28068 82609 82...
output:
224806
result:
ok single line: '224806'
Test #12:
score: 0
Accepted
time: 20ms
memory: 17440kb
input:
90000 1 45387 45388 59683 59684 54643 54644 48430 48431 46674 46675 75808 75809 83944 83945 37142 37143 7492 7493 35485 35486 13045 13046 77367 77368 89390 89391 53121 53122 81728 81729 64058 64059 64306 64307 82272 82273 44564 44565 87969 87970 81932 81933 63077 63078 30731 30732 41593 41594 77746 ...
output:
131664
result:
ok single line: '131664'
Subtask #4:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 17ms
memory: 11060kb
input:
20000 300 2298 16922 18552 10941 5144 7836 2466 9076 15500 13240 2610 15368 46 12878 8306 1607 9979 8975 2496 19531 11248 4651 4852 18243 7396 1470 7610 10848 10295 14356 4459 5642 4890 16696 3731 3723 762 4227 13780 8107 13906 2311 9823 2028 15526 1892 6024 10011 9630 9756 9126 15139 14648 115 9097...
output:
25452 25423 25440 25429 25431 25431 25436 25441 25434 25440 25434 25437 25434 25441 25428 25436 25442 25440 25431 25441 25435 25438 25441 25436 25434 25440 25431 25439 25441 25427 25435 25439 25435 25438 25434 25433 25437 25438 25437 25447 25435 25432 25447 25430 25434 25437 25437 25433 25439 25440 ...
result:
wrong answer 1st lines differ - expected: '25404', found: '25452'
Subtask #5:
score: 0
Wrong Answer
Test #19:
score: 19
Accepted
time: 13ms
memory: 13484kb
input:
65535 65535 1811 13118 468 385 23933 56882 4701 42452 49582 14109 22804 8146 20990 13165 2862 42235 19741 48554 50898 55957 62662 44085 48624 14885 7097 61368 19900 36151 553 50630 52087 31138 45875 33789 57834 46368 50259 10233 56656 29222 48661 58651 62042 50198 5077 28414 50381 15211 60800 37526 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 65535 lines
Test #20:
score: -19
Wrong Answer
time: 30ms
memory: 11348kb
input:
65535 4945 42941 23543 45541 34209 47644 12262 63786 38185 22551 3126 54952 11257 17620 53826 57165 30291 59502 23927 492 5929 64283 64528 57715 29045 63287 26916 59711 10374 25832 3012 35364 52502 43385 51892 37943 19200 33799 9796 56123 63643 35588 2879 38798 22405 12420 21846 39766 20399 51516 62...
output:
98232 98304 98157 98254 98283 98230 98251 98188 98235 98281 98231 98211 98258 98180 98278 98284 98211 98237 98164 98239 98233 98160 98254 98236 98213 98158 98301 98279 98258 98286 98227 98266 98164 98218 98183 98276 98253 98231 98245 98237 98182 98235 98258 98280 98279 98203 98210 98286 98275 98301 ...
result:
wrong answer 1st lines differ - expected: '98244', found: '98232'
Subtask #6:
score: 17
Accepted
Test #24:
score: 17
Accepted
time: 41ms
memory: 14668kb
input:
100000 100000 48535 38306 85495 24582 10294 14137 41148 31842 32266 36977 2963 82055 78886 1396 81175 93259 80317 66239 83481 49641 35645 57424 97195 2160 53900 55968 4256 17352 95865 83196 64417 63683 64041 61292 3392 82881 22755 53454 71067 1268 2191 84847 66432 7544 15405 77351 50616 64123 97980 ...
output:
117138 -1 -1 117137 -1 -1 117136 -1 117143 117147 -1 117140 117137 117142 117141 117143 117143 117146 117141 117148 -1 -1 -1 -1 -1 117139 -1 -1 117136 117140 -1 117143 117139 -1 117138 117144 117139 117140 117142 117139 117137 117143 117140 117139 -1 117145 117139 -1 117138 117146 -1 117139 -1 -1 -1...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 41ms
memory: 15496kb
input:
100000 100000 72307 73730 4855 4669 34268 96202 34918 23630 58362 7732 92176 59135 16689 72302 33132 12243 48675 9923 34563 32938 24208 16343 64499 63821 23234 49559 3460 7884 15643 37549 3876 9935 7104 38075 30639 45757 11276 82078 44582 39679 5148 26538 12388 75198 13093 12579 689 34845 40881 4717...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 100000 lines
Test #26:
score: 0
Accepted
time: 47ms
memory: 15604kb
input:
99979 99979 69202 47860 39855 52164 18328 74890 31688 46109 92086 80635 54583 49627 78582 65772 55284 63334 59151 62688 36773 4827 25295 9565 53053 55879 24104 2366 63525 48588 88429 62276 29770 1586 3678 32824 37114 59808 93856 89974 4984 39208 71382 89255 16691 91672 30302 38180 79117 81553 15869 ...
output:
-1 134868 134867 134866 134865 134864 134863 134862 134861 134860 134859 134858 134857 134856 134855 134854 134853 134852 134851 134850 134849 134848 134847 134846 134845 134844 134843 134842 134841 134840 134839 134838 134837 134836 134835 134834 134833 134832 134831 134830 134831 134832 134833 134...
result:
ok 99979 lines
Test #27:
score: 0
Accepted
time: 50ms
memory: 15792kb
input:
99975 99975 84557 86723 42801 26572 67888 15221 48648 69192 68067 93925 16045 51384 58962 42032 14845 68807 55756 60858 68142 58918 60181 23602 53314 3146 37119 41042 58602 95241 18410 18613 40247 31786 46533 89929 22780 6461 43282 118 68236 71460 84977 63500 81859 79007 45493 29856 74394 90025 1498...
output:
134301 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 99975 lines
Subtask #7:
score: 0
Skipped
Dependency #1:
0%