QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#760631 | #9565. Birthday Gift | Meowmeowmeow# | RE | 0ms | 0kb | C++20 | 2.1kb | 2024-11-18 18:02:04 | 2024-11-18 18:02:06 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200005
map<int,int>p[MAXN];
vector<int>v[MAXN];
#define pb push_back
int n,m,nn;
int b[MAXN];
int r[MAXN];
bool bp[MAXN];
int w[MAXN];
set<int>s;
signed main() {
int T;
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while(T --) {
for(int i = 0; i <= n; i ++) {
bp[i] = 0; w[i] = 0;
b[i] = 0; r[i] = 0; p[i].clear();
v[i].clear();
}
s.clear();
cin >> nn >> m >> n;
for(int i = 1; i <= nn; i ++) {
cin >> b[i];
bp[b[i]] = 1;
}
int at = 0,an = 0;
for(int i = 1; i <= m; i ++) {
int x,y;
cin >> x >> y;
if(bp[x] && bp[y]) at ++;
if(x == y) {
w[x] ++;
continue;
}
v[x].pb(y);
v[y].pb(x);
p[x][y] ++;
p[y][x] ++;
}
for(int i = 1; i <= n; i ++)
r[i] = w[i];
for(int i = 1; i <= nn; i ++) {
int x = b[i];
for(auto y:v[x]) {
r[y] ++;
}
}/*
cout<<at<<"\n";
for(int i = 1; i <= n; i ++)
cout<<r[i]<<" ";
cout<<"\n";*/
for(int i = 1; i <= n; i ++)
if(!bp[i]) {
s.insert(-(r[i]*1000000+i));
}
an = at;
for(int i = 1; i <= n; i ++)
if(!bp[i]) {
s.erase(-(r[i]*1000000+i));
int ax = (-*s.begin())/1000000;
an = max(an,ax+r[i]+at);
for(auto y:v[i])
if(!bp[y]) {
// cout<<i<<" "<<y<<" "<<r[i]<<" "<<r[y]<<" "<<p[i][y]<<"\n";
an = max(an,at+r[i]+r[y]+p[i][y]);
}
s.insert(-(r[i]*1000000+i));
}
cout<<an<<"\n";
}
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
*/
詳細信息
Test #1:
score: 0
Runtime Error
input:
5 0110101 01020102 0000021111 1012121010 0100202010