QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773995#2683. British Menuyinpeichu2021WA 6ms18800kbC++142.4kb2024-11-23 11:11:002024-11-23 11:11:01

Judging History

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

  • [2024-11-23 11:11:01]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：18800kb
查看
  • [2024-11-23 11:11:00]
  • 提交

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+1;i<=cnt;i++)if(sum[i]>5)while(1);
	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)
		for(int j:scc[i])q.push(j);
	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;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 17836kb

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: 2ms
memory: 18168kb

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: 0ms
memory: 17060kb

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: 2ms
memory: 17948kb

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: 0ms
memory: 17964kb

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: 6ms
memory: 18788kb

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: 0ms
memory: 17880kb

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: 0ms
memory: 16824kb

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: 18516kb

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: 0ms
memory: 16852kb

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: 0ms
memory: 18328kb

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: 0ms
memory: 18344kb

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: 18800kb

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: 2ms
memory: 15204kb

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: 0ms
memory: 17072kb

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: 0ms
memory: 17940kb

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: 0ms
memory: 18596kb

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: 2ms
memory: 15488kb

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: -100
Wrong Answer
time: 4ms
memory: 18156kb

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:

211

result:

wrong answer 1st lines differ - expected: '244', found: '211'
English 繁體中文 简体中文

Server Time: 2024-11-29 22:30:13 | OpenSource Project