QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734010#9573. Social Mediarose_DKYTL 143ms8632kbC++201.5kb2024-11-10 23:03:162024-11-10 23:03:16

Judging History

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

  • [2024-11-10 23:03:16]
  • 评测
  • 测评结果：TL
  • 用时：143ms
  • 内存：8632kb
查看
  • [2024-11-10 23:03:16]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MAXN 200005
#define endl '\n'
int n,m,k;
int a[MAXN],uu[MAXN],vv[MAXN],b[MAXN];
vector<ll>e[MAXN];
void solve()
{
	map<int,bool>frd;
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++) a[i]=0,e[i].clear();
	for(int i=1;i<=n;i++){
		ll x;
		cin>>x;
		frd[x]=1;
	}
	int ans=0;
	map<pair<int,int>,int>kind;	
	for(int i=1;i<=m;i++){
		cin>>uu[i]>>vv[i];
		if(!frd[uu[i]]&&!frd[vv[i]]){
			e[uu[i]].push_back(vv[i]);
			e[vv[i]].push_back(uu[i]);
		}

		if(frd[uu[i]]&&frd[vv[i]]){
			ans++;
			continue;
		}
		kind[{uu[i],vv[i]}]++;
		if(frd[vv[i]]) a[uu[i]]++;
		if(frd[uu[i]]) a[vv[i]]++;
	}
	for(int i=1;i<=k;i++){
		if(frd[i]) b[i]=0;
		else b[i]=a[i]+kind[{i,i}];
	}
	sort(b+1,b+k+1);
	
	ll tmp=0;
	for(int i=1;i<=k;i++){
		if(frd[i]) continue;
		ll jl=b[k];
		if(a[i]+kind[{i,i}]==b[k]) jl=b[k-1];
		tmp=max(tmp,a[i]+kind[{i,i}]+jl);
		for(int j=0;j<e[i].size();j++){
			ll v=e[i][j];
			if(frd[v]||i==v) continue;			
			ll res=a[i]+a[v]+kind[{i,v}]+kind[{v,i}]+kind[{i,i}]+kind[{v,v}];
			tmp=max(tmp,res);
		}	
	}
	cout<<ans+tmp<<endl;
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	
	
	return 0;
}
/**
5
4 12 7
5 7 3 6
3 6 
2 2
1 4
2 4
1 3
7 6
4 1
5 4
1 1
1 1
2 1
3 7
2 7 6
2 4
1 2
3 2
2 5
5 4
2 6
4 6
2 6
1 1 2
1
1 2
2 1 2
1 2
1 2
2 1 100
24 11
11 24
 */
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
4 12 7
5 7 3 6
3 6
2 2
1 4
2 4
1 3
7 6
4 1
5 4
1 1
1 1
2 1
3 7
2 7 6
2 4
1 2
3 2
2 5
5 4
2 6
4 6
2 6
1 1 2
1
1 2
2 1 2
1 2
1 2
2 1 100
24 11
11 24

output:

9
5
1
1
1

result:

ok 5 number(s): "9 5 1 1 1"

Test #2:

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

input:

10000
19 12 20
8 12 1 5 11 7 17 13 19 6 3 9 10 15 14 20 4 18 16
4 11
7 1
8 4
16 19
1 13
15 2
16 2
8 7
3 15
11 13
5 20
18 14
17 14 20
2 9 1 12 8 11 10 17 18 16 3 15 5 14 20 13 7
15 10
3 2
5 16
7 8
6 1
6 4
18 16
1 8
4 1
20 6
6 9
4 15
7 5
14 9
1 3 18
9
15 18
17 15
11 14
7 19 7
3 1 2 5 6 4 7
5 1
4 5
3 1...

output:

12
14
1
19
6
5
1
11
19
4
3
10
4
1
4
19
15
2
18
4
17
5
1
2
5
17
3
2
6
15
6
3
6
4
4
7
3
7
4
1
16
15
2
3
6
12
12
7
6
8
8
6
8
11
16
1
4
9
8
14
2
6
19
19
16
8
20
14
8
12
7
9
6
8
2
17
9
5
5
3
6
6
20
8
13
11
10
5
3
6
3
1
8
5
8
11
7
14
10
9
9
11
7
9
5
2
8
14
10
5
3
5
5
10
1
6
9
16
5
3
19
1
4
8
8
10
4
2
1
15...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 82ms
memory: 5960kb

input:

1000
59 96 80
10 66 50 63 15 2 28 41 21 58 45 42 14 79 32 33 37 52 1 74 57 27 72 77 8 49 40 78 31 12 70 62 73 26 69 24 3 65 67 23 6 47 17 38 54 80 5 64 13 51 44 71 39 34 75 19 55 30 68
61 14
14 26
7 28
53 3
51 79
68 24
50 1
39 45
74 18
13 12
5 68
41 1
32 30
69 13
61 59
26 68
17 56
74 14
22 25
71 41
...

output:

60
83
4
5
2
90
23
125
72
7
49
81
25
9
40
22
78
51
7
47
77
19
49
73
134
114
104
121
180
3
2
4
92
86
146
9
20
2
74
3
78
32
19
63
5
79
17
16
54
131
83
23
45
153
33
137
67
98
8
21
6
53
12
89
14
97
9
142
25
100
108
87
56
15
43
153
2
165
41
132
116
160
118
167
63
6
16
8
3
67
4
91
4
34
8
83
32
34
119
63
17...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 143ms
memory: 8632kb

input:

100
37 237 517
339 497 190 114 508 454 321 58 102 392 289 207 291 459 16 320 55 378 269 63 407 244 397 101 357 328 412 62 70 468 457 21 253 453 509 169 400
202 476
217 222
418 58
440 109
90 110
266 197
159 398
412 317
259 239
500 34
178 508
329 162
192 409
467 144
223 300
2 289
96 366
191 427
142 12...

output:

6
4
11
6
6
7
11
11
2
3
14
2
4
2
3
2
2
5
7
3
3
5
3
13
8
7
17
6
2
8
3
9
3
10
2
3
3
2
2
2
5
12
2
5
5
959
369
56
1045
15
67
394
757
82
1008
56
2
1317
1590
217
37
345
32
515
103
326
1628
1450
293
12
397
358
403
420
220
150
392
588
3
978
1296
97
49
1377
7
1764
627
1652
188
65
11
12
2
2
1
5
1
2
2
2

result:

ok 100 numbers

Test #5:

score: -100
Time Limit Exceeded

input:

1
100 200000 200000
9411 13081 102149 19907 193611 24114 159730 105867 96529 35050 21890 102981 87777 182418 96659 118374 76106 107614 179526 45826 56158 33510 42240 53971 75573 98727 113513 35449 165290 167552 180720 151348 194140 132021 197828 138348 52399 151728 27676 75498 122825 15163 89905 262...

output:

2

result:
English 繁體中文 简体中文

Server Time: 2025-01-21 07:14:19 | OpenSource Project