QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#774020#2683. British Menuyinpeichu2021AC ✓1738ms59432kbC++142.3kb2024-11-23 11:18:422024-11-23 11:18:43

Judging History

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

  • [2024-11-23 11:18:43]
  • 评测
  • 测评结果：AC
  • 用时：1738ms
  • 内存：59432kb
查看
  • [2024-11-23 11:18:42]
  • 提交

answer

#include<bits/stdc++.h>
// #define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
#define MAXN 300005
int head[MAXN],ver[MAXN*4],nextt[MAXN*4],tot;
void add(int x,int y){
	ver[++tot]=y;
	nextt[tot]=head[x];
	head[x]=tot;
}
int n,m,ru[MAXN],f[MAXN],ans;
int dfn[MAXN],low[MAXN],num,st[MAXN];
int top,col[MAXN],sum[MAXN],cnt;
vector<int>scc[MAXN];
void tarjan(int x){
	dfn[x]=low[x]=++num;
	st[++top]=x;
	for(int i=head[x];i;i=nextt[i]){
		int v=ver[i];
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}else if(!col[v])low[x]=min(low[x],dfn[v]);
	}
	if(low[x]==dfn[x]){
		cnt++;
		sum[cnt]++,col[x]=cnt;
		scc[cnt].push_back(x);
		while(st[top]!=x){
			sum[cnt]++,col[st[top]]=cnt;
			scc[cnt].push_back(st[top]);
			top--;
		}
		top--;
	}
}
bool vis[MAXN],fl[MAXN];
map<int,map<int,int> >mp;
void dfs(int x,int s,int c,int fr){
	vis[x]=1;
	mp[fr][x]=max(mp[fr][x],s);
	for(int i=head[x];i;i=nextt[i]){
		int v=ver[i];
		if(col[v]==c&&!vis[v])dfs(v,s+1,c,fr);
	}
	vis[x]=0;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		ru[y]++,add(x,y);
	}
	for(int i=1;i<=n;i++)add(i,n+1);ru[n+1]=n;
	cnt=n+1;
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=nextt[j]){
			int v=ver[j];
			if(col[v]&&col[v]!=col[i])ru[col[v]]++;
		}
	for(int i=n+2;i<=cnt;i++)
		for(int x:scc[i])dfs(x,0,i,x);
	for(int i=1;i<=n+1;i++)f[i]=1;
	queue<int>q;
	for(int i=1;i<=n;i++)
		if(ru[i]==0&&!col[i])q.push(i);
	for(int i=n+2;i<=cnt;i++)if(ru[i]==0)q.push(scc[i][0]);
	while(!q.empty()){
		int x=q.front();q.pop();
		if(!col[x]){
			for(int i=head[x];i;i=nextt[i]){
				int v=ver[i];
				f[v]=max(f[v],f[x]+1);
				if(!col[v]&&--ru[v]==0)q.push(v);
				if(col[v]&&--ru[col[v]]==0)q.push(v);
			}
		}else{
			for(int b:scc[col[x]]){
				for(int i=head[b];i;i=nextt[i]){
					int v=ver[i];
					if(col[v]==col[x])continue;
					for(int a:scc[col[x]])
						f[v]=max(f[v],f[a]+mp[a][b]+1);
					if(!col[v]&&--ru[v]==0)q.push(v);
					if(col[v]&&--ru[col[v]]==0)q.push(v);
				}
			}
		}
	}
	cout<<f[n+1]-1;
//	for(int i=1;i<=n+1;i++)ans=max(ans,f[i]),cout<<f[i]<<' ';
//	cout<<'\n';
//	cout<<ans;
//	cout<<'\n';
//	for(int i=1;i<=n;i++,cout<<'\n')
//		for(int j=1;j<=n;j++)
//			cout<<mp[i][j]<<' ';
	
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

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

input:

10 6
7 8
4 2
8 6
5 1
4 1
4 5

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 16944kb

input:

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

output:

5

result:

ok single line: '5'

Test #3:

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

input:

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

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 0ms
memory: 16916kb

input:

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

output:

6

result:

ok single line: '6'

Test #5:

score: 0
Accepted
time: 3ms
memory: 18824kb

input:

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

output:

8

result:

ok single line: '8'

Test #6:

score: 0
Accepted
time: 0ms
memory: 17944kb

input:

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

output:

9

result:

ok single line: '9'

Test #7:

score: 0
Accepted
time: 3ms
memory: 18352kb

input:

12 11
11 10
12 10
8 12
9 12
5 7
1 6
8 11
9 11
7 9
7 11
2 9

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 4ms
memory: 17952kb

input:

7 7
1 2
2 3
3 4
4 5
5 6
6 2
4 7

output:

6

result:

ok single line: '6'

Test #9:

score: 0
Accepted
time: 0ms
memory: 15328kb

input:

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

output:

8

result:

ok single line: '8'

Test #10:

score: 0
Accepted
time: 3ms
memory: 16848kb

input:

7 9
1 2
2 3
3 4
4 5
5 6
6 2
4 7
6 4
3 5

output:

7

result:

ok single line: '7'

Test #11:

score: 0
Accepted
time: 3ms
memory: 18920kb

input:

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

output:

7

result:

ok single line: '7'

Test #12:

score: 0
Accepted
time: 3ms
memory: 18536kb

input:

100 600
1 81
1 48
1 64
1 74
1 30
1 58
1 53
1 46
1 76
1 66
1 51
1 68
1 99
1 71
1 41
1 44
1 47
1 19
3 54
4 83
4 33
4 63
4 83
4 29
5 18
5 80
5 49
5 60
5 11
5 78
5 62
5 89
5 45
6 40
6 50
6 21
6 52
6 97
6 49
6 98
6 5
6 43
6 46
6 2
6 19
6 81
7 92
7 34
7 97
7 63
7 2
8 97
9 87
9 3
9 2
10 3
10 90
12 37
12 88...

output:

90

result:

ok single line: '90'

Test #13:

score: 0
Accepted
time: 3ms
memory: 17284kb

input:

100 600
1 14
1 38
1 60
1 56
1 48
1 64
3 34
3 40
3 26
3 11
3 11
4 98
4 30
4 8
4 17
4 39
4 99
4 28
4 24
4 17
4 6
5 50
5 3
5 33
5 97
5 45
5 94
5 93
5 86
5 58
6 60
6 70
6 79
6 61
6 55
6 31
6 87
6 65
6 48
6 61
7 41
7 21
7 34
7 36
7 87
7 10
7 58
7 31
8 55
8 96
8 44
8 20
8 44
8 20
8 42
9 22
9 92
9 60
9 78
...

output:

86

result:

ok single line: '86'

Test #14:

score: 0
Accepted
time: 3ms
memory: 15124kb

input:

100 600
1 53
1 20
1 56
1 32
1 27
1 18
1 73
1 21
1 9
1 66
2 24
2 85
2 30
2 71
2 26
2 24
2 17
2 63
2 92
3 56
3 82
3 93
3 98
3 29
4 55
4 28
4 55
4 60
4 6
5 46
5 22
5 63
5 77
6 29
6 57
6 39
6 41
6 18
6 15
6 63
6 39
7 4
7 38
7 37
7 52
8 98
8 15
8 82
8 54
8 98
9 6
9 79
9 52
9 25
9 69
9 28
9 82
9 93
9 54
1...

output:

84

result:

ok single line: '84'

Test #15:

score: 0
Accepted
time: 3ms
memory: 18132kb

input:

200 1200
1 141
1 75
1 187
1 175
1 150
1 23
1 23
1 76
1 138
1 52
1 172
1 155
1 32
2 106
3 155
3 77
3 96
3 69
3 88
3 80
3 128
3 83
3 11
3 117
3 33
3 107
3 126
3 164
3 76
4 5
4 121
4 86
4 37
4 10
4 84
4 112
4 43
4 80
4 104
4 194
4 63
4 142
5 156
5 83
5 112
5 37
6 13
6 93
6 7
6 77
7 166
7 179
7 67
7 49
...

output:

168

result:

ok single line: '168'

Test #16:

score: 0
Accepted
time: 3ms
memory: 16824kb

input:

200 1200
1 126
1 142
1 58
1 48
1 99
1 96
1 159
2 60
2 111
2 151
2 47
2 158
2 84
2 80
2 119
2 74
3 15
3 108
3 135
3 85
3 127
3 85
3 55
3 16
3 195
4 71
4 156
4 183
5 61
5 125
5 25
5 84
5 183
5 183
5 175
5 17
6 85
7 187
7 21
7 62
7 103
7 110
7 111
8 94
8 194
8 40
8 99
8 55
8 85
8 151
9 65
9 183
9 135
9...

output:

158

result:

ok single line: '158'

Test #17:

score: 0
Accepted
time: 3ms
memory: 18220kb

input:

200 900
1 36
1 68
1 141
2 63
3 137
3 24
3 145
3 53
3 151
3 101
3 18
3 141
4 42
4 147
4 96
4 114
4 158
4 81
5 80
5 177
5 113
5 8
5 101
5 100
5 59
6 170
6 21
6 8
6 109
6 48
8 157
8 140
8 87
8 139
8 158
8 27
8 62
8 116
8 134
8 185
8 25
9 146
9 120
11 52
11 164
11 184
11 56
11 29
11 33
12 175
12 187
12 ...

output:

163

result:

ok single line: '163'

Test #18:

score: 0
Accepted
time: 6ms
memory: 18336kb

input:

500 2200
4 290
12 52
15 380
14 168
19 265
16 425
20 340
17 444
22 456
28 463
30 234
34 403
32 149
39 28
40 409
53 38
51 335
54 316
60 35
57 389
63 235
64 87
68 370
70 357
66 214
67 167
71 128
71 187
74 397
75 31
78 65
85 484
81 64
85 455
99 152
96 251
100 178
102 406
104 492
102 316
104 234
101 445
...

output:

282

result:

ok single line: '282'

Test #19:

score: 0
Accepted
time: 0ms
memory: 18392kb

input:

500 2200
2 78
1 177
3 63
4 448
4 489
3 222
3 412
6 495
14 331
20 114
16 215
18 431
32 167
42 87
44 440
42 282
44 118
52 40
52 186
62 467
70 182
69 291
70 447
70 316
79 226
80 331
78 286
82 372
85 124
88 370
87 106
90 336
90 217
94 256
92 483
92 160
95 407
100 437
97 27
102 209
101 397
104 128
101 38...

output:

244

result:

ok single line: '244'

Test #20:

score: 0
Accepted
time: 3ms
memory: 17936kb

input:

500 2200
3 457
2 43
4 36
3 285
5 384
1 428
9 354
9 92
6 377
9 321
11 483
21 9
24 275
30 491
27 85
26 52
26 106
27 409
30 24
35 429
43 114
42 247
48 412
50 353
50 45
53 275
51 416
55 140
56 79
60 302
60 489
65 247
70 253
71 123
71 304
75 172
78 450
78 43
85 260
85 392
94 487
97 29
98 224
99 138
101 3...

output:

306

result:

ok single line: '306'

Test #21:

score: 0
Accepted
time: 5ms
memory: 17620kb

input:

1000 4400
5 42
4 934
7 538
10 308
18 305
18 942
16 636
18 569
34 56
35 71
31 118
40 552
39 909
36 831
41 448
41 380
50 850
47 814
51 319
58 719
60 890
60 130
56 555
68 869
66 566
70 712
66 667
67 684
69 874
68 547
74 900
71 865
83 483
83 360
88 275
86 65
87 889
96 155
96 179
104 408
101 993
104 234
...

output:

573

result:

ok single line: '573'

Test #22:

score: 0
Accepted
time: 10ms
memory: 18484kb

input:

1000 4400
4 80
3 178
3 65
5 449
2 222
1 911
2 617
3 908
7 376
6 482
15 357
15 480
18 236
20 847
17 168
27 979
37 51
37 102
37 316
39 369
44 940
41 639
43 421
43 523
42 104
41 309
45 751
42 75
44 809
41 568
46 840
47 995
58 639
61 476
69 184
68 449
79 289
79 111
78 671
85 874
89 609
87 727
93 258
93 ...

output:

593

result:

ok single line: '593'

Test #23:

score: 0
Accepted
time: 10ms
memory: 15312kb

input:

1000 4400
1 457
2 44
1 46
8 879
10 323
8 873
8 202
7 33
6 210
27 493
32 761
31 846
34 940
43 411
42 750
41 550
43 78
50 913
51 430
53 637
54 156
54 312
54 229
55 722
56 79
56 451
64 748
62 658
70 972
66 379
70 209
66 151
73 673
72 800
79 446
78 976
77 564
79 253
84 392
90 158
94 939
98 722
99 137
98...

output:

525

result:

ok single line: '525'

Test #24:

score: 0
Accepted
time: 879ms
memory: 55164kb

input:

100000 500000
3 65318
1 19774
4 56143
3 27477
2 66862
3 34511
2 76591
1 56859
1 11598
2 33175
5 90199
9 19871
7 30148
10 26315
14 29551
20 51962
16 75601
20 4020
16 95616
19 55973
20 18515
17 80626
24 4613
25 61458
22 11326
25 24273
21 516
25 72845
22 37499
24 17325
21 42855
22 29413
25 30168
25 376...

output:

70924

result:

ok single line: '70924'

Test #25:

score: 0
Accepted
time: 876ms
memory: 57508kb

input:

100000 500000
3 18846
1 82679
1 67785
3 73320
2 71819
1 80210
4 44774
4 6711
2 53916
5 52553
5 95822
3 4357
1 50521
6 16919
6 34797
10 25690
10 27529
15 51652
11 80890
15 74044
13 60362
15 52840
16 77619
16 52536
18 69737
18 3980
19 82645
20 31323
18 31089
17 99288
19 14249
24 99693
24 26336
22 3934...

output:

70304

result:

ok single line: '70304'

Test #26:

score: 0
Accepted
time: 442ms
memory: 37848kb

input:

50000 300000
5 23418
1 19744
1 29122
3 38245
3 16530
3 25610
2 31060
3 2306
5 20071
3 29041
1 19529
5 23277
4 36964
5 28056
1 7348
2 37755
5 25980
3 39620
4 41176
2 10185
2 46902
3 2044
1 28523
5 5142
5 42711
9 28933
6 43220
10 31681
6 16971
9 12460
6 22023
9 11042
6 19426
8 47756
8 12865
8 34589
7 ...

output:

38743

result:

ok single line: '38743'

Test #27:

score: 0
Accepted
time: 444ms
memory: 37980kb

input:

50000 300000
2 16785
3 3319
5 34817
3 33333
2 10364
1 20064
4 11693
3 23332
4 32379
5 12131
2 15090
5 43654
2 36880
2 16280
1 8846
5 9284
5 8779
5 36260
2 19004
2 19142
5 9055
9 16759
10 11123
9 33459
9 805
10 41383
6 22065
6 1731
11 37179
11 26548
13 13701
17 28878
17 33002
22 29331
23 43490
24 471...

output:

38824

result:

ok single line: '38824'

Test #28:

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

input:

2 1
2 1

output:

2

result:

ok single line: '2'

Test #29:

score: 0
Accepted
time: 0ms
memory: 18860kb

input:

2 2
2 1
1 2

output:

2

result:

ok single line: '2'

Test #30:

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

input:

98258 1
75482 12373

output:

2

result:

ok single line: '2'

Test #31:

score: 0
Accepted
time: 527ms
memory: 43100kb

input:

100000 1000000
58672 21176
20731 88265
52507 90000
16081 73720
67959 90455
47627 17416
50588 67160
12078 68707
56096 41693
50447 56296
33761 35518
8044 61126
97751 24915
36818 15329
82647 25462
65613 33515
62977 14856
9772 29027
63357 16174
19955 24081
31175 77188
80579 93282
78344 10962
6536 93375
...

output:

100000

result:

ok single line: '100000'

Test #32:

score: 0
Accepted
time: 518ms
memory: 42900kb

input:

100000 1000000
28046 29608
68140 67810
27204 20304
92632 53245
74349 15576
58978 89209
51471 30196
16789 42658
84999 56153
94003 95820
60063 35247
21557 92835
39943 35753
33587 11411
36217 98286
56486 54479
94646 31591
24178 18844
62789 77734
6138 89268
45804 84805
51715 9515
22224 44581
67091 81008...

output:

57784

result:

ok single line: '57784'

Test #33:

score: 0
Accepted
time: 883ms
memory: 51748kb

input:

100000 1000000
75901 15551
33200 34329
60662 88593
69707 21311
21990 90701
73021 58490
23071 21996
97277 98560
35896 44448
24764 67514
79309 3770
40571 31919
51371 29675
85795 22166
53161 87315
9131 72856
70077 97740
2252 99772
24281 6344
6446 86620
15896 62366
35754 50991
54853 43795
65692 1077
983...

output:

318

result:

ok single line: '318'

Test #34:

score: 0
Accepted
time: 849ms
memory: 54568kb

input:

100000 1000000
81519 81935
13438 79852
15388 3964
95682 68698
4874 51768
91607 60878
71432 13918
47774 64404
39 27597
16133 29435
19587 24679
11060 9982
3977 36140
57169 71379
33051 19691
40193 86092
82515 78905
58066 44959
90863 91281
93006 81933
63164 9649
75414 8828
98059 15929
26636 34502
93495 ...

output:

578

result:

ok single line: '578'

Test #35:

score: 0
Accepted
time: 1151ms
memory: 58848kb

input:

100000 1000000
4575 4572
99658 99656
31370 50411
77040 91354
283 13599
24348 24350
54944 87810
62523 63285
45762 95447
69854 90067
4575 94077
13305 53330
18520 95885
49573 60399
21466 78036
30729 96652
24817 67819
18336 91188
58354 97702
55746 55747
16789 16790
4460 50959
31119 46453
32464 93367
879...

output:

693

result:

ok single line: '693'

Test #36:

score: 0
Accepted
time: 1337ms
memory: 57592kb

input:

100000 1000000
14625 32970
91844 42625
53813 59772
82384 10093
65483 73866
36185 75700
27957 23992
74505 54447
39661 25560
95647 95399
2034 91742
96554 62656
2397 82691
47933 88856
33159 26830
9925 45819
14742 53060
21939 70335
64609 82402
20072 36489
46545 52446
26332 83752
53083 27930
17447 65856
...

output:

700

result:

ok single line: '700'

Test #37:

score: 0
Accepted
time: 1738ms
memory: 59432kb

input:

100000 1000000
30087 77098
13279 57063
6566 96317
343 49884
51601 79682
55614 48541
36834 86830
55286 64282
93073 74767
4124 750
36251 40205
68981 64793
72817 26655
41140 36896
70462 44328
55862 63361
59423 65285
12018 65860
74657 79775
1785 96587
794 20860
43236 13825
90573 57355
7150 88719
50293 9...

output:

650

result:

ok single line: '650'

Test #38:

score: 0
Accepted
time: 731ms
memory: 24576kb

input:

1412 998987
689 934
994 952
1284 682
678 950
1297 1151
13 537
1017 1103
36 1408
31 1337
429 29
229 662
275 473
983 67
613 786
1245 448
952 629
13 1382
229 1087
681 963
877 494
1359 96
675 399
919 313
692 565
966 1055
974 507
436 217
1198 852
601 435
1362 445
625 427
978 722
947 497
915 527
431 1222
...

output:

1412

result:

ok single line: '1412'
English 繁體中文 简体中文

伺服器時間: 2024-11-29 22:48:56 | 開源專案