QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#754144 | #9573. Social Media | yeah14 | WA | 59ms | 3672kb | C++17 | 2.5kb | 2024-11-16 14:19:49 | 2024-11-16 14:19:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull long long
#define PII pair<int ,int>
const int INF = 0x3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int fp(int a, int x, int mod) {
int ans = 1;
while (x) {
if (x & 1)ans *= a;
ans %= mod;
a *= a;
a %= mod;
x >>= 1;
}
return ans;
}
struct ff
{
int w, i, nxt;
bool operator<(const ff a) {
if (w != a.w)return w < a.w;
else return nxt < a.nxt;
}
};
priority_queue<ff>q;
bool fr[N];
int cnt[N];
int cntt[N];
map<PII,int>po;
int id[N];
bool cmp(int a, int b) {
if (cnt[a] != cnt[b])return cnt[a] > cnt[b];
else return fr[a] < fr[b];
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
int now=0;
for (int i = 1; i <= k+5; i++) {
id[i] = i;
cnt[i] = 0;
cntt[i] = 0;
fr[i] = 0;
}
po.clear();
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
fr[a] = 1;
}
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
po[{ a,b }]++;
po[{ b,a }]++;
if (fr[a] && fr[b])now++;
else if (fr[a]) {
cnt[b]++;
cntt[b]++;
}
else if (fr[b]) {
cnt[b]++;
cntt[a]++;
}
else if (a == b) {
cnt[a]++;
cntt[a]++;
}
else {
cnt[a]++;
cnt[b]++;
}
}
sort(id+1, id + k + 1,cmp);
int pp = k - n;
if (pp == 0||now==m) {
cout << now << endl;
return;
}
int ans = 0;
if (pp == 1) {
cout << now + cnt[id[1]] << endl;
return;
}
for (int i = 1; i <= pp; i++) {
if (fr[id[i]])continue;
for (int j = i+1; j <=pp; j++) {
if (fr[id[j]])continue;
ans = max(cntt[id[i]] + cntt[id[j]] + po[{id[i], id[j]}],ans);
//cout << cntt[id[i]] + cntt[id[j]] + po[{id[i], id[j]}] << " " << id[i] << " " << id[j] << endl;
}
}
cout << ans + now << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
/*
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: 100
Accepted
time: 0ms
memory: 3672kb
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: -100
Wrong Answer
time: 59ms
memory: 3628kb
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 9 4 1 4 19 14 2 13 4 17 4 1 2 5 17 3 2 3 15 6 3 2 4 2 7 3 7 4 1 16 15 2 3 6 12 11 7 6 7 8 6 8 11 16 1 4 6 8 14 2 6 19 15 16 8 20 14 8 12 7 4 6 8 2 17 9 5 5 3 6 6 20 8 13 11 10 5 3 6 3 1 6 5 8 11 7 14 10 9 9 11 7 9 5 2 8 11 10 5 3 5 5 10 1 6 9 16 5 3 19 1 4 8 8 10 4 2 1 14 ...
result:
wrong answer 12th numbers differ - expected: '10', found: '9'