QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302757#952. Spring cleaningmonster_hunter35 50ms18628kbC++142.6kb2024-01-11 11:18:502024-01-11 11:18:51

Judging History

你现在查看的是最新测评结果

  • [2024-01-11 11:18:51]
  • 评测
  • 测评结果:35
  • 用时:50ms
  • 内存:18628kb
  • [2024-01-11 11:18:50]
  • 提交

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%