QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#754144#9573. Social Mediayeah14WA 59ms3672kbC++172.5kb2024-11-16 14:19:492024-11-16 14:19:51

Judging History

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

  • [2024-11-16 14:19:51]
  • 评测
  • 测评结果:WA
  • 用时:59ms
  • 内存:3672kb
  • [2024-11-16 14:19:49]
  • 提交

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'