Codeforces Global Round 19 E. Best Pair

48 阅读 0 评论 32 点赞

我是靠谱客的博主甜美路人，最近开发中收集的这篇文章主要介绍Codeforces Global Round 19 E. Best Pair，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<bits/stdc++.h>
using namespace std;
// #define int long long 
const int N=3e5+10;
int t,n,m,a[N];
vector<int> v[N];
unordered_map<int,int> mp;
map<pair<int,int>,int> ban;
bool cmp(int a,int b){return a>b;}
struct node{
    int a,b,c;
    bool operator < (const node &A) const {
        return A.a>a;
    }
};

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        mp.clear();ban.clear();
        for(int i=1;i<=n;i++) v[i].clear();
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),mp[a[i]]++;
        for(auto it:mp) v[it.second].push_back(it.first);
        for(int i=0;i<=n;i++) sort(v[i].begin(),v[i].end(),cmp);
        for(int i=1;i<=m;i++){
            int x,y;scanf("%d%d",&x,&y);
            ban[{x,y}]=ban[{y,x}]=1;
        }
        long long  res=0;
        for(int i=0;i<=n;i++){
            if(v[i].size()==0) continue;
            for(int j=i;j<=n;j++){
                if(v[j].size()==0) continue;
                // while(q.size()) q.pop();
                priority_queue<node> q;
                // cout<<i<<" "<<j<<" "<<v[i][0]<<" "<<v[j][0]<<endl;
                map<pair<int,int>,int> vis;
                q.push({v[i][0]+v[j][0],0,0});
                while(q.size()){
                    auto tp=q.top();q.pop();
                    int k=tp.b,l=tp.c;
                    // cout<<i<<" "<<j<<" "<<v[i][k]<<" "<<v[j][l]<<endl;
                    vis[{k,l}]=vis[{l,k}]=1;
                    if(ban.count({v[i][k],v[j][l]})==0&&v[i][tp.b]!=v[j][tp.c]){
                        // cout<<i<<" "<<j<<" "<<v[i][k]<<" "<<v[j][l]<<"OK"<<endl;
                        res=max(res,(long long)(tp.a*((long long)i+j)));
                        break;
                    }
                    if(l+1<v[j].size()&&!vis[{k,l+1}]) q.push({v[i][k]+v[j][l+1],k,l+1}),vis[{k,l+1}]=1;
                    if(k+1<v[i].size()&&!vis[{k+1,l}]) q.push({v[i][k+1]+v[j][l],k+1,l}),vis[{k+1,l}]=1;
                }
            }
        }
        cout<<res<<endl;

    }
}