QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#123382	#5654. Italian Data Centers	zswzswzsw	AC ✓	5ms	3644kb	C++14	920b	2023-07-12 14:28:48	2023-07-12 14:28:49

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 14:28:49]
评测

测评结果：AC
用时：5ms
内存：3644kb

查看

[2023-07-12 14:28:48]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int val[N];
int d[2][N],ans;
vector<int>G[N];
int n,m,k;
struct node{
	int opt,u;
};
int hd,tl;
node que[N*N];
void BFS(int s)
{
	hd=1;tl=0;
	for(int i=1;i<=n;i++)d[0][i]=d[1][i]=-1;
	d[0][s]=0;que[++tl]=(node){0,s};
	while(hd<=tl)
	{
		int u=que[hd].u,opt=que[hd++].opt;
		for(int i=0,v,nxt;i<G[u].size();i++){
			v=G[u][i];nxt=opt^(val[u]!=val[v]);
			if(d[nxt][v]!=-1)continue;
			d[nxt][v]=d[opt][u]+1;
			que[++tl]=(node){nxt,v};
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=1;j++)if(d[j][i]==-1)d[j][i]=d[j^1][i]+k;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k;j++)
		ans=max(ans,min(d[0][i]+j,d[1][i]+k-j));
	return;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=1,x,y;i<=m;i++)cin>>x>>y,G[x].push_back(y),G[y].push_back(x);
	for(int i=1;i<=n;i++)BFS(i);
	cout<<ans;
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3432kb

input:

output:

result:

ok single line: '1'

Test #2:

score: 0

Accepted

time: 1ms

memory: 3416kb

input:

output:

result:

ok single line: '2'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3412kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 1ms

memory: 3424kb

input:

8 14 100
3 3 2 2 1 2 2 1
2 7
1 5
7 8
4 6
2 8
1 8
2 6
6 7
1 6
1 4
3 5
1 3
4 5
5 7

output:

result:

ok single line: '53'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3420kb

input:

output:

result:

ok single line: '3'

Test #6:

score: 0

Accepted

time: 1ms

memory: 3400kb

input:

40 50 2
3 1 1 2 1 2 1 2 2 2 1 3 2 3 2 3 3 2 3 1 2 1 2 1 1 3 2 2 1 2 1 1 3 2 2 3 1 3 1 2
36 14
14 35
37 12
15 21
2 1
39 5
28 35
32 40
6 13
4 24
11 26
30 31
20 22
3 27
40 19
34 29
8 21
38 12
38 7
23 29
26 18
4 6
17 22
12 10
38 10
19 14
17 28
27 7
11 8
34 20
25 37
2 34
24 18
16 25
16 2
5 30
13 33
24 36...

output:

result:

ok single line: '11'

Test #7:

score: 0

Accepted

time: 1ms

memory: 3432kb

input:

40 200 4
2 3 3 2 3 2 3 3 2 2 2 2 3 3 2 3 1 2 1 2 3 2 3 3 2 1 3 1 3 1 2 1 1 3 1 1 3 3 2 2
17 21
7 5
24 4
15 22
35 22
34 6
14 17
37 2
2 23
29 21
1 8
38 1
8 29
35 4
39 31
6 1
25 2
35 14
37 27
21 26
2 22
10 8
33 8
1 14
23 12
13 10
6 15
26 1
15 10
34 12
1 29
3 5
20 4
24 31
20 1
1 13
35 27
13 32
36 11
36 ...

output:

result:

ok single line: '5'

Test #8:

score: 0

Accepted

time: 2ms

memory: 3412kb

input:

40 350 7
1 1 1 1 3 1 1 1 3 3 2 2 3 2 1 3 3 1 1 1 2 1 3 1 1 2 2 2 2 1 1 3 1 3 1 3 3 1 2 2
2 11
11 28
28 4
27 31
15 1
15 27
24 19
33 38
6 19
18 5
29 28
20 28
7 28
6 34
33 6
39 17
38 4
13 20
40 21
18 21
1 27
17 35
21 11
39 7
15 8
20 31
23 5
11 26
28 3
25 11
13 33
20 32
10 28
12 26
23 10
33 12
6 39
3 18...

output:

result:

ok single line: '6'

Test #9:

score: 0

Accepted

time: 1ms

memory: 3416kb

input:

40 480 50
1 1 2 2 3 2 2 1 1 3 1 3 1 2 3 2 2 3 3 2 2 3 2 3 1 2 2 1 1 2 3 2 1 1 1 2 2 1 3 3
34 4
33 39
5 25
3 25
10 29
16 21
26 34
15 37
21 18
34 12
15 8
20 40
25 1
14 5
7 20
15 31
17 36
12 15
35 11
18 1
38 31
37 19
1 4
10 8
36 11
24 35
7 12
40 3
27 25
16 10
30 12
5 9
33 19
35 34
33 12
35 32
27 11
12 ...

output:

result:

ok single line: '27'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

40 610 66
1 1 1 2 2 3 3 3 2 3 1 2 3 2 2 1 1 1 2 1 2 1 1 1 1 1 3 1 3 3 2 3 3 1 3 1 3 3 2 3
24 13
12 29
3 40
4 15
20 12
4 17
36 31
23 21
24 31
31 33
27 5
1 4
21 34
9 11
23 37
34 28
11 22
12 8
8 21
39 25
13 16
21 32
11 28
15 26
25 9
17 15
24 37
1 21
12 2
30 13
36 15
26 2
5 20
40 1
32 11
12 5
9 15
29 38...

output:

result:

ok single line: '35'

Test #11:

score: 0

Accepted

time: 1ms

memory: 3432kb

input:

40 720 97
1 2 1 2 2 3 3 1 3 2 2 3 1 3 3 1 1 3 3 1 1 3 2 3 3 3 1 1 2 3 3 2 3 2 1 3 3 1 1 1
1 5
28 6
29 3
18 23
6 23
31 12
31 32
12 3
3 19
36 30
27 1
30 3
19 33
17 18
13 15
28 8
9 25
3 20
28 22
27 5
19 7
34 19
15 29
37 13
36 10
2 26
16 18
5 34
10 22
36 7
29 40
39 17
27 6
20 17
23 40
16 8
31 18
23 34
2...

output:

result:

ok single line: '51'

Test #12:

score: 0

Accepted

time: 1ms

memory: 3420kb

input:

100 99 0
3 2 2 3 3 3 1 1 3 2 3 3 3 2 2 1 2 2 3 2 3 2 1 1 3 2 1 2 2 1 2 3 3 2 1 3 1 1 2 3 2 2 1 2 1 3 3 2 1 2 2 1 2 3 1 1 3 2 1 3 3 1 2 2 2 1 3 1 2 2 3 3 3 2 1 1 1 2 3 1 1 2 2 3 1 2 1 2 3 3 3 2 3 2 2 2 3 1 1 3
84 52
79 95
54 16
93 9
28 69
77 3
41 40
41 23
67 53
53 58
37 54
13 83
63 38
7 89
6 66
38 14...

output:

result:

ok single line: '85'

Test #13:

score: 0

Accepted

time: 2ms

memory: 3424kb

input:

100 99 100
1 1 2 3 1 3 1 2 3 1 3 1 1 3 3 1 2 1 2 3 3 2 2 2 1 3 1 1 2 2 1 3 2 1 2 2 3 3 2 1 3 3 2 3 3 2 1 2 3 1 1 3 1 3 3 2 1 2 3 3 3 1 2 3 1 2 1 3 1 2 2 3 2 2 2 2 2 3 3 1 2 1 2 2 2 3 2 3 1 3 1 3 2 3 3 1 3 3 2 3
26 52
11 10
45 56
38 10
27 2
92 86
64 39
47 55
31 9
35 81
90 32
3 51
23 50
68 57
95 9
63 ...

output:

result:

ok single line: '114'

Test #14:

score: 0

Accepted

time: 2ms

memory: 3456kb

input:

100 4950 0
2 1 1 2 2 3 1 3 3 2 2 1 2 3 2 2 2 2 1 3 3 3 1 2 3 2 3 2 3 3 2 2 3 1 1 1 1 1 3 3 2 3 3 2 1 3 1 1 1 2 2 3 3 2 1 3 3 2 1 1 2 1 1 2 1 3 2 3 3 1 3 1 3 3 3 2 3 1 1 1 2 1 1 1 2 2 1 1 1 2 2 3 2 3 2 1 1 1 1 2
15 26
99 4
65 30
27 7
58 79
92 86
76 60
47 89
11 58
78 63
99 47
47 32
3 23
84 36
16 83
46...

output:

result:

ok single line: '1'

Test #15:

score: 0

Accepted

time: 5ms

memory: 3616kb

input:

100 4950 100
1 1 2 3 1 2 3 3 2 2 1 3 1 1 2 3 2 3 1 2 3 3 2 2 3 3 1 1 3 3 2 1 2 3 3 1 3 2 2 3 1 1 2 2 2 2 3 1 2 2 2 1 3 2 2 3 2 2 1 2 2 2 1 3 3 2 3 3 3 3 3 3 2 2 3 3 2 3 1 1 3 1 3 2 3 3 3 1 3 3 3 3 2 1 2 1 2 1 1 2
17 50
60 10
1 93
60 77
80 74
26 90
40 65
29 20
31 70
21 75
98 3
64 68
4 57
16 12
70 86
...

output:

result:

ok single line: '52'

Test #16:

score: 0

Accepted

time: 2ms

memory: 3420kb

input:

100 1000 45
1 1 3 2 2 3 2 1 1 3 3 2 1 2 3 2 1 3 3 2 3 3 2 2 1 1 2 1 2 3 3 1 1 3 3 1 2 3 3 2 1 2 2 1 1 1 3 3 1 3 3 3 1 1 1 2 1 1 1 1 3 1 2 2 2 2 3 1 2 1 2 2 2 1 1 1 3 1 2 2 2 1 3 2 3 1 2 3 1 2 2 1 2 2 3 2 1 2 3 1
12 66
89 81
14 24
72 20
43 51
72 91
94 56
74 95
47 1
2 81
81 74
1 78
82 97
72 5
52 57
20...

output:

result:

ok single line: '25'

Test #17:

score: 0

Accepted

time: 3ms

memory: 3556kb

input:

100 1001 99
1 3 1 1 2 1 2 3 3 2 2 1 1 3 1 1 3 1 3 2 3 3 2 3 1 3 2 3 3 2 2 3 2 2 3 1 3 2 1 1 1 2 3 2 3 1 1 2 1 3 3 1 2 3 2 3 2 3 3 1 2 3 2 1 1 3 1 1 1 3 1 2 3 2 1 2 2 2 2 3 3 3 3 1 2 3 2 1 1 2 2 1 2 2 3 3 1 1 1 3
58 74
37 90
23 27
11 81
99 94
44 31
29 21
77 10
95 90
91 6
45 1
90 62
10 72
56 50
39 88
...

output:

result:

ok single line: '52'

Test #18:

score: 0

Accepted

time: 1ms

memory: 3560kb

input:

100 2000 44
1 3 3 2 3 2 3 2 3 3 3 2 3 3 1 1 2 2 2 1 1 1 1 1 2 3 1 2 3 2 1 1 2 1 2 3 2 1 1 2 2 3 3 2 2 2 2 1 1 3 1 3 3 2 1 3 3 2 3 1 3 3 2 3 1 1 3 2 3 2 2 3 2 2 2 3 1 1 2 3 1 3 2 3 2 2 2 1 3 2 1 2 1 3 3 2 2 2 3 3
88 34
19 40
9 57
33 25
66 19
73 10
74 18
52 98
65 22
89 5
58 100
24 8
85 53
95 94
68 49
...

output:

result:

ok single line: '24'

Test #19:

score: 0

Accepted

time: 1ms

memory: 3460kb

input:

100 2001 98
3 3 1 3 3 3 1 1 1 1 2 3 2 3 3 2 1 1 2 3 2 2 2 3 3 2 2 1 1 2 2 1 3 1 3 1 3 2 1 1 1 1 3 2 1 3 1 3 3 3 2 3 1 3 1 3 1 1 2 1 3 1 1 3 3 1 1 3 2 3 3 1 1 2 2 2 2 3 3 3 1 1 3 2 2 1 3 1 2 2 3 3 2 3 1 2 3 1 2 1
42 45
47 98
12 95
41 42
73 76
36 50
21 80
96 100
84 25
80 65
88 77
70 55
93 51
9 38
42 5...

output:

result:

ok single line: '51'

Test #20:

score: 0

Accepted

time: 4ms

memory: 3364kb

input:

100 3000 46
1 1 3 3 3 3 3 1 3 2 2 2 3 2 3 1 1 1 1 3 1 1 2 2 2 3 3 2 3 3 3 2 3 1 1 1 2 2 3 3 1 1 3 3 3 1 1 2 1 1 3 2 1 3 1 2 2 1 2 2 2 2 2 2 2 3 3 3 1 1 3 3 1 1 2 3 3 3 1 1 3 2 2 2 3 1 2 3 3 2 1 2 1 2 3 1 2 2 2 1
91 93
53 87
86 26
4 93
53 85
58 88
88 93
79 25
16 83
48 63
82 2
97 12
14 23
42 75
38 30
...

output:

result:

ok single line: '25'

Test #21:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

100 3001 97
2 3 2 1 1 1 1 2 1 1 2 2 1 3 1 1 2 3 2 2 1 2 1 3 1 3 1 3 3 3 3 2 2 1 3 3 2 2 3 1 1 2 2 1 1 3 2 1 1 2 2 1 3 3 1 2 3 1 2 1 1 1 3 1 3 3 1 3 3 3 1 3 1 1 3 2 3 3 1 3 1 1 3 3 3 1 3 2 1 2 2 3 2 2 3 3 3 3 3 3
76 9
13 42
82 74
3 24
11 10
49 31
50 11
2 3
21 81
32 51
82 44
18 97
1 9
32 62
45 50
48 9...

output:

result:

ok single line: '51'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3312kb

input:

13 14 0
1 1 1 1 1 1 1 1 1 1 3 3 1
7 8
5 6
2 12
4 5
6 7
3 4
1 13
1 3
11 12
8 9
1 11
9 10
2 10
2 13

output:

result:

ok single line: '6'

Test #23:

score: 0

Accepted

time: 1ms

memory: 3428kb

input:

13 14 3
1 1 1 1 1 1 2 1 3 3 1 2 3
11 12
12 13
9 10
1 7
2 10
2 13
3 4
2 6
8 9
5 6
4 5
7 8
1 11
1 3

output:

result:

ok single line: '8'

Test #24:

score: 0

Accepted

time: 0ms

memory: 3428kb

input:

13 14 6
1 1 1 2 2 1 2 1 1 1 1 3 1
9 10
7 8
6 7
10 11
1 3
8 9
1 13
4 5
2 12
2 3
11 12
2 13
5 6
1 4

output:

result:

ok single line: '12'

Test #25:

score: 0

Accepted

time: 1ms

memory: 3436kb

input:

13 14 50
1 1 1 1 3 1 2 1 2 3 1 3 1
2 4
10 11
8 9
3 4
9 10
7 8
1 5
11 12
5 6
1 3
6 7
2 13
2 12
1 13

output:

result:

ok single line: '31'

Test #26:

score: 0

Accepted

time: 1ms

memory: 3420kb

input:

13 14 75
1 1 1 2 1 1 2 3 1 2 3 1 2
8 9
4 5
2 13
10 11
1 4
9 10
6 7
11 12
7 8
2 5
12 13
1 6
2 3
1 3

output:

result:

ok single line: '81'

Test #27:

score: 0

Accepted

time: 1ms

memory: 3536kb

input:

13 14 100
1 1 1 1 1 1 1 1 1 1 1 2 3
2 8
1 9
5 6
6 7
3 4
7 8
1 3
12 13
2 13
1 11
2 10
4 5
11 12
9 10

output:

result:

ok single line: '56'

Test #28:

score: 0

Accepted

time: 1ms

memory: 3552kb

input:

100 101 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 2 1 1 2 1 2 1 2 1 3 3 3 1 2 1 2 2 1 1 2 1 3 1 1 2 2 1 2 2 2 1 1 3 3 1 3 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
20 21
42 43
77 78
70 71
3 4
8 9
49 50
40 41
92 93
34 35
72 73
1 3
95 96
39 40
53 54
16 17
...

output:

result:

ok single line: '43'

Test #29:

score: 0

Accepted

time: 2ms

memory: 3592kb

input:

100 101 50
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 2 2 1 2 3 1 1 2 1 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
1 68
25 26
33 34
29 30
38 39
71 72
91 92
32 33
23 24
55 56
1 3
88 89
83 84
58 59
20 21
48...

output:

result:

ok single line: '70'

Test #30:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

100 101 97
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 2 2 1 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1
29 30
62 63
89 90
52 53
51 52
44 45
17 18
37 38
56 57
78 79
45 46
71 72
4 5
6 7
92 93
26 ...

output:

result:

ok single line: '98'

Test #31:

score: 0

Accepted

time: 2ms

memory: 3312kb

input:

100 101 98
1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 2 1 3 1 2 3 3 2 2 3 2 2 3 3 3 3 2 1 3 3 2 2 3 2 2 2 2 3 2 1 1 1 1 2 2 1 3 2 1 1 2 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
80 81
83 84
10 11
37 38
22 23
51 52
58 59
41 42
31 32
52 53
90 91
98 99
96 97
86 87
12 13...

output:

result:

ok single line: '99'

Test #32:

score: 0

Accepted

time: 2ms

memory: 3420kb

input:

100 101 99
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 2 3 3 3 1 2 2 3 3 1 3 3 3 3 1 2 2 1 3 3 2 2 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
47 48
58 59
34 35
14 15
54 55
88 89
38 39
60 61
16 17
97 98
71 72
72 73
7 8
57 58
6 7
99 ...

output:

result:

ok single line: '137'

Test #33:

score: 0

Accepted

time: 2ms

memory: 3588kb

input:

100 101 100
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 2 1 3 2 3 3 1 3 2 1 1 2 2 1 2 2 1 3 2 2 1 1 3 1 2 3 3 1 3 2 1
94 95
45 46
17 18
79 80
52 53
5 6
27 28
72 73
1 3
31 32
2 69
86 87
84 85
55 56
76 77
34 ...

output:

result:

ok single line: '149'

Test #34:

score: 0

Accepted

time: 1ms

memory: 3396kb

input:

2 1 0
2 1
1 2

output:

result:

ok single line: '1'

Test #35:

score: 0

Accepted

time: 0ms

memory: 3364kb

input:

2 1 1
3 2
1 2

output:

result:

ok single line: '2'

Test #36:

score: 0

Accepted

time: 1ms

memory: 3416kb

input:

output:

result:

ok single line: '2'

Test #37:

score: 0

Accepted

time: 1ms

memory: 3584kb

input:

output:

result:

ok single line: '3'

Test #38:

score: 0

Accepted

time: 1ms

memory: 3412kb

input:

output:

result:

ok single line: '3'