QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#760631#9565. Birthday GiftMeowmeowmeow#RE 0ms0kbC++202.1kb2024-11-18 18:02:042024-11-18 18:02:06

Judging History

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

  • [2024-11-18 18:02:06]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-18 18:02:04]
  • 提交

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

output:


result: