QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123581#5651. Parmigiana With SeafoodzswzswzswAC ✓75ms11696kbC++141.0kb2023-07-12 23:27:002023-07-12 23:27:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 23:27:01]
  • 评测
  • 测评结果:AC
  • 用时:75ms
  • 内存:11696kb
  • [2023-07-12 23:27:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
long long read(void)
{
	char ch=getchar();long long sum=0;bool f=0;
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')f=1,ch=getchar();
	while(ch>='0'&&ch<='9')sum=sum*10+ch-'0',ch=getchar();
	if(f)sum=-sum;return sum;
}
const int N=101000;
int n;
bool tg[N];
int dep[N],is[N];
vector<int>G[N];
bool DFS(int u,int f){
	bool fl=1;
	int cnt=0;is[u]=tg[u];dep[u]=dep[f]+1;
	if(tg[u]&&((dep[u]-1)&1))return 0;
	for(int v:G[u])if(v!=f){
		fl&=DFS(v,u);cnt+=is[v];
		is[u]|=is[v];
	}
	if(u!=n&&dep[u]%2&&cnt>=2)fl=0;
	if(u==n&&cnt>=3)fl=0;
	return fl;
	
}
bool chk(int t){
	for(int i=1;i<=n;i++)tg[i]=(i>=t),is[i]=0;
	return DFS(n,0)^1;
}
int main()
{
	n=read();
	for(int i=1,x,y;i<=n-1;i++)x=read(),y=read(),G[x].push_back(y),G[y].push_back(x);
	if(!(n&1))return cout<<n,0;
	int L=1,R=n;
	for(int i=1;i<=n;i++)if(G[i].size()==1)L=max(L,i);
	while(L<R){
		int mid=(L+R+1)>>1;
		if(chk(mid))L=mid;
		else R=mid-1;
	}cout<<L;
	return 0;
	
}
/*
7
7 1
1 5
1 6
1 2
1 3
2 4
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5912kb

input:

4
1 2
1 3
1 4

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 6012kb

input:

5
1 5
5 3
3 4
4 2

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 11ms
memory: 10196kb

input:

99999
81856 39633
81856 94012
99999 43062
99946 220
81856 46131
99933 36505
99939 35662
99952 70971
99999 3275
99938 58416
99976 66658
99991 87922
81856 80992
99933 6392
99951 41047
99970 54115
81856 38150
99934 73554
81856 64578
81856 18576
99951 67996
99938 84479
81856 39617
99999 18664
99946 2505...

output:

99925

result:

ok single line: '99925'

Test #4:

score: 0
Accepted
time: 75ms
memory: 11696kb

input:

99997
90325 59106
22545 8765
88871 37709
14739 95233
8778 29659
48110 57549
91258 76066
15724 65144
48244 87291
12076 94378
41946 96707
93645 12812
53817 34343
72097 94062
81212 263
78713 78150
6754 94906
20957 97539
59293 5018
77961 78090
57262 95225
79349 47902
99024 7869
10613 13728
61757 41090
4...

output:

85398

result:

ok single line: '85398'

Test #5:

score: 0
Accepted
time: 35ms
memory: 10036kb

input:

97687
5206 6282
79497 65247
26426 93558
88096 86680
12934 32573
14514 39078
1619 40141
52678 92737
31478 91858
85427 62603
83477 53003
38500 72325
62910 10306
97005 13325
38472 67023
39728 18368
78232 5993
20560 1752
22173 38357
97114 10935
4680 13734
45188 13484
58025 44787
70778 20
11932 28511
416...

output:

96849

result:

ok single line: '96849'

Test #6:

score: 0
Accepted
time: 20ms
memory: 9536kb

input:

84671
62167 4590
83269 18308
7577 37508
52720 9931
12966 65554
23617 73916
76954 20353
72074 331
3246 58164
41679 28021
41713 36414
53221 77575
53398 66400
21562 16390
11317 20458
70409 48081
43608 84144
4665 70292
65863 62926
53700 32839
82581 18581
56748 30899
75093 58023
10481 13121
60945 8777
26...

output:

84200

result:

ok single line: '84200'

Test #7:

score: 0
Accepted
time: 24ms
memory: 9068kb

input:

73167
47092 28182
66083 3885
43535 13437
54796 24969
69017 27959
4701 13449
69154 70617
71864 8320
65436 18607
63511 58647
49371 16640
57598 9646
69711 6405
44171 46975
10159 72030
72806 67302
70130 62361
61032 23019
22551 71530
15388 46131
2466 41213
7614 7234
7187 68699
69979 18867
73006 9719
7307...

output:

72317

result:

ok single line: '72317'

Test #8:

score: 0
Accepted
time: 45ms
memory: 9588kb

input:

93127
82031 39720
66956 8709
23978 63403
6145 91337
85068 90000
5292 12192
75403 59013
61717 17385
31485 21675
59006 14085
89359 30804
37788 78960
3732 89293
22416 42721
82075 58210
66360 6744
52855 52426
54146 17777
36605 38752
39355 66859
9092 76915
53782 42274
3786 12113
56898 61989
41242 22010
8...

output:

91965

result:

ok single line: '91965'

Test #9:

score: 0
Accepted
time: 43ms
memory: 9412kb

input:

86317
86251 61689
82938 40996
86188 54210
45740 2544
77938 54345
86029 74462
20990 10621
47220 64502
25410 52112
28478 79354
65823 29158
65047 50464
77800 67525
63557 20923
819 43262
68885 63609
39859 33970
33434 26781
35723 54011
85477 27761
64717 2822
33013 20762
22073 14737
67127 32412
14005 3609...

output:

84672

result:

ok single line: '84672'

Test #10:

score: 0
Accepted
time: 34ms
memory: 8996kb

input:

74629
8981 58746
51934 71958
42 26665
13900 16642
57253 62024
22275 58881
12554 22042
61621 36223
32622 35482
14516 3563
45558 3566
28335 31184
28248 10881
45042 46848
59481 4622
50919 21331
28687 6561
34021 51558
71196 18928
31797 14009
74085 4248
25090 1379
62704 62972
74594 49508
17713 1594
39171...

output:

72873

result:

ok single line: '72873'

Test #11:

score: 0
Accepted
time: 63ms
memory: 9652kb

input:

96347
70983 70118
35876 62696
59956 62763
27376 77120
66808 47665
39671 56799
6860 47977
40369 46341
61183 40118
29514 95936
60415 74331
3282 87508
5076 517
1587 1472
92469 70513
13064 90639
35694 77684
9991 64568
51144 75207
80446 4901
39289 76282
95044 27742
30796 71955
43159 31242
37228 54527
453...

output:

93303

result:

ok single line: '93303'

Test #12:

score: 0
Accepted
time: 49ms
memory: 9264kb

input:

86315
23636 66376
78321 16476
59862 46509
35991 14497
68245 40007
25790 45975
37852 32748
56994 48908
81313 36605
3612 55724
43578 62393
48271 80771
31107 85554
71483 22883
60614 73294
41342 41801
17755 41818
16279 57284
77832 75097
15380 26582
68024 23118
67365 36785
35465 20314
22013 73293
26710 7...

output:

84885

result:

ok single line: '84885'

Test #13:

score: 0
Accepted
time: 45ms
memory: 9028kb

input:

76483
57191 19964
14611 24128
25765 7767
76283 48878
36658 43451
41049 8603
68423 1270
15797 45182
53254 15427
52395 45391
66393 11910
72490 44472
25331 44526
20296 54363
37458 73782
23820 30214
17192 57858
10260 1396
14704 3869
74433 30769
52255 65492
28516 12405
68838 65057
17033 33652
48323 57658...

output:

74362

result:

ok single line: '74362'

Test #14:

score: 0
Accepted
time: 66ms
memory: 9740kb

input:

96457
66415 25458
68078 16946
35330 29485
49899 33975
76008 76800
24989 51232
70892 65062
44164 3515
28101 58669
34773 43789
72826 90397
24596 44064
4565 75203
85204 73903
62960 1927
8859 16252
65483 85608
33500 34085
42732 80213
62736 93780
2693 29938
21343 56564
6325 11543
91086 13097
6758 50608
4...

output:

94207

result:

ok single line: '94207'

Test #15:

score: 0
Accepted
time: 52ms
memory: 9504kb

input:

86317
31642 30091
24803 61615
84744 40779
63344 16094
7516 59801
59074 59722
82518 45343
9365 75630
55874 45064
48583 21682
35891 63615
37762 57886
10164 66056
31686 83350
74145 66390
64564 18847
64257 11636
55777 62474
27478 38720
47770 71914
6090 32749
56009 25492
54088 25302
65078 53816
14331 730...

output:

83681

result:

ok single line: '83681'

Test #16:

score: 0
Accepted
time: 46ms
memory: 8924kb

input:

76131
45293 8648
42498 3644
64424 6336
39972 62488
74491 1992
29911 55761
58294 66772
39736 55781
11756 60696
68986 27810
53268 9992
31784 68630
69790 15464
53864 72072
30165 13294
41257 62659
27342 16293
57222 28415
28053 7899
5233 40127
65350 39789
67195 66268
69673 23704
70139 7624
13045 12969
32...

output:

73807

result:

ok single line: '73807'

Test #17:

score: 0
Accepted
time: 71ms
memory: 10304kb

input:

97561
96667 64196
82167 53227
3029 64138
37099 76940
31039 96877
57012 86559
2332 87568
49910 39932
4725 50907
16790 56229
65911 24234
45367 49582
20322 80074
64150 70798
76786 13938
96883 6378
85558 65411
40306 56830
47427 93982
79798 67314
36216 66540
81428 37896
97445 84803
27554 50317
66830 1371...

output:

91563

result:

ok single line: '91563'

Test #18:

score: 0
Accepted
time: 60ms
memory: 9804kb

input:

86321
45853 71073
52193 73686
3348 68109
71013 17256
21929 39520
35078 65546
58829 52347
18655 46475
24141 83337
82973 69298
39776 76305
72685 29155
21443 50080
10653 78730
14488 54273
20531 38751
23480 26986
24275 25702
58648 47501
83199 21654
28284 11457
68023 697
53989 19743
11850 4952
65941 7505...

output:

81149

result:

ok single line: '81149'

Test #19:

score: 0
Accepted
time: 55ms
memory: 8936kb

input:

71235
10214 33273
594 62256
55772 22729
66989 57868
4836 39513
55570 48718
57593 18158
32181 50917
32228 44198
39887 35899
34146 59729
42903 5313
63415 63788
56179 22710
40714 11646
42548 8839
36080 57056
51374 6787
18772 50944
69916 17986
60712 6422
41252 5053
59410 6498
15019 6872
12310 30428
6289...

output:

66746

result:

ok single line: '66746'

Test #20:

score: 0
Accepted
time: 1ms
memory: 6172kb

input:

2
2 1

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 2ms
memory: 6416kb

input:

3
1 3
3 2

output:

2

result:

ok single line: '2'

Test #22:

score: 0
Accepted
time: 2ms
memory: 5912kb

input:

3
1 2
2 3

output:

3

result:

ok single line: '3'

Test #23:

score: 0
Accepted
time: 2ms
memory: 5768kb

input:

11
4 10
10 7
7 11
11 6
6 9
9 3
11 5
5 8
8 1
8 2

output:

8

result:

ok single line: '8'

Test #24:

score: 0
Accepted
time: 8ms
memory: 8984kb

input:

100000
80252 67279
6717 83032
494 90986
23424 56083
39247 21279
38855 8884
1472 73422
57343 77904
87413 17678
64938 75713
40993 26255
18901 97511
87268 12622
94075 15610
42757 18865
3925 58291
15451 18499
57467 32134
71764 66696
42637 56217
284 41710
95975 56053
72325 75370
13516 51979
5671 69112
56...

output:

100000

result:

ok single line: '100000'

Test #25:

score: 0
Accepted
time: 16ms
memory: 9152kb

input:

94678
94641 46446
94668 45165
94629 37628
90558 65885
94645 52923
90558 70146
90558 9417
90558 81294
94661 65337
94612 24135
90558 31797
94618 1331
90558 21554
94629 93206
90558 11665
94668 64989
90558 67846
90558 62243
94608 37513
94629 28
90558 63385
94668 76717
94670 22923
94641 74517
94618 89607...

output:

94678

result:

ok single line: '94678'

Test #26:

score: 0
Accepted
time: 15ms
memory: 8988kb

input:

93468
53665 42040
60171 70686
77901 1078
3910 23230
83105 58047
88030 65667
26114 6020
27930 87897
22134 87279
76778 56744
70151 84587
20886 46424
69117 46344
49892 23343
67491 58734
67004 28406
86979 14137
14511 84736
62430 75393
6271 87137
37688 41370
72391 21794
83703 50615
59406 91488
17084 9019...

output:

93468

result:

ok single line: '93468'