Submission #527836

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct BIT{
    int N;
    vector<int>bit;
    void init(int n){
        N=n;
        bit.resize(N,0);
    }
    void inc(int k){
        for(k++;k<=N;k+=k&-k)bit[k]++;
    }
    void dec(int k){
        for(k++;k<=N;k+=k&-k)bit[k]--;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=bit[k];
        return ret;
    }
};

struct UF{
    int N;
    vector<int>par,sz;
    void init(int n){
        N=n;
        par.resize(N);
        sz.resize(N,1);
        for(int i=0;i<N;i++)par[i]=i;
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};

vector<int>G[100000];
bool used[100000];
BIT bit;
set<pair<int,int> >S;


int solve(vector<int>&vec){
    int ret=0;
    for(int i=0;i<vec.size();i++){
        ret+=i-bit.sum(vec[i]-1);
        bit.inc(vec[i]);
    }
    for(int i=0;i<vec.size();i++){
        bit.dec(vec[i]);
    }
    return ret;
}


int best_swap(signed N, signed M,signed E[][2]){
    for(int i=0;i<M;i++){
        int a=E[i][0],b=E[i][1];
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i=0;i<N;i++){
        sort(G[i].begin(),G[i].end());
        G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
    }

    UF uf;uf.init(N);
    for(int i=0;i<M;i++){
        int a=E[i][0],b=E[i][1];
        if(S.find(pair<int,int>(min(a,b),max(a,b)))!=S.end())continue;
        if(uf.same(a,b))return -1;
        uf.unite(a,b);
        S.insert(pair<int,int>(min(a,b),max(a,b)));
    }

    for(int i=0;i<N;i++){
        if(G[i].size()>2)return -1;
    }

    int ans=0;
    bit.init(N);
    vector<int>vec;
    for(int i=0;i<N;i++){
        if(used[i]||G[i].size()>1)continue;
        vec.clear();
        int x=i;
        while(true){
            vec.push_back(x);
            used[x]=true;
            int y=-1;
            for(int i=0;i<G[x].size();i++){
                int tmp=G[x][i];
                if(!used[tmp]){
                    y=tmp;
                    break;
                }
            }
            if(y==-1)break;
            x=y;
        }
        int val1=solve(vec);
        reverse(vec.begin(),vec.end());
        int val2=solve(vec);
        ans+=min(val1,val2);
    }

    return ans;
}
/*
int N,M,E[100000][2];
signed main(){
    cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        E[i][0]=a;E[i][1]=b;
    }


    cout<<best_swap(N,M,E)<<endl;

    return 0;
}
*/

Submission Info

Judge Result