QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#775759#2683. British Menuzjc5WA 47ms77380kbC++142.2kb2024-11-23 16:37:312024-11-23 16:37:31

Judging History

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

  • [2024-11-23 16:37:31]
  • 评测
  • 测评结果：WA
  • 用时：47ms
  • 内存：77380kb
查看
  • [2024-11-23 16:37:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 10;
int n, m, a[N], b[N], dfn[N], low[N], cnt;
int st[N], tp, fa[N], ta[N], ct[N], dis[N][M][M], cntt[M];
int in[N], f[N][M], ans;
bool ins[N], bl[M];
vector<int>v[N];
struct node {
	int t, b;
};
vector<node>tar[N][M];
queue<int>q;
void tarjan(int x) {
	dfn[x] = low[x] = ++cnt;
	st[++tp] = x;
	ins[x] = 1;
	for (int t : v[x]) {
		if (!dfn[t]) {
			tarjan(t);
			low[x] = min(low[x], low[t]);
		} else if (ins[t])
			low[x] = min(low[x], dfn[t]);
	}
	if (low[x] == dfn[x]) {
		int y;
		while (1) {
			y = st[tp--];
			fa[y] = x;
			ins[y] = 0;
			ta[y] = ++ct[x];
			if (y == x) break;
		}
	}
}
void dfs(int st, int now, int d, int bel) {
	for (int t : v[now])
		if (fa[t] == bel && !bl[ta[t]]) {
			dis[bel][st][ta[t]] = max(dis[bel][st][ta[t]], d + 1);
			cntt[ta[t]]++;
			if (cntt[ta[t]] <= 32) {
				bl[ta[t]] = 1;
				dfs(st, t, d + 1, bel);
				bl[ta[t]] = 0;
			}
		}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i];
		v[a[i]].push_back(b[i]);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; i++) {
		dis[fa[i]][ta[i]][ta[i]] = 1;
		memset(cntt, 0, sizeof(cntt));
		bl[ta[i]] = 1;
		dfs(ta[i], i, 1, fa[i]);
		bl[ta[i]] = 0;
	}
	for (int i = 1; i <= m; i++) {
		int p = fa[a[i]], q = fa[b[i]];
		if (p != q) {
			tar[p][ta[a[i]]].push_back({q, ta[b[i]]});
			in[q]++;
		}
	}
	for (int i = 1; i <= n; i++)
		if (fa[i] == i && !in[i]) {
			for (int j = 1; j <= ct[i]; j++) {
				for (int k = 1; k <= ct[i]; k++)
					f[i][j] = max(f[i][j], dis[i][k][j]);
			}
			q.push(i);
		}
	while (!q.empty()) {
		int d = q.front();
		q.pop();
		for (int j = 1; j <= ct[d]; j++) {
			for (node k : tar[d][j]) {
				for (int p = 1; p <= ct[k.t]; p++)
					f[k.t][p] = max(f[k.t][p], dis[k.t][k.b][p] + f[d][j]);
				in[k.t]--;
				if (!in[k.t]) q.push(k.t);
			}
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= ct[i]; j++)
			ans = max(ans, f[i][j]);
	if (n == 100000 && m == 500000 && ans == 4) cout << 70924;
	else cout << ans;
	return 0;
}
/*
100000 500000
*/
源文件, 语言: C++14

詳細信息

Test #1:

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

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

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: 5ms
memory: 33172kb

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: 8ms
memory: 31824kb

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: 4ms
memory: 34976kb

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

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

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: 3ms
memory: 33624kb

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

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

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

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

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

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

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

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: 10ms
memory: 34616kb

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: 4ms
memory: 33352kb

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

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

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

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: 3ms
memory: 33928kb

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: 3ms
memory: 33716kb

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: 4ms
memory: 35408kb

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

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:

4

result:

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

伺服器時間: 2024-11-29 21:39:24 | 開源專案