Submission #527828

---

Source Code Expand

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

int bit_n,bit[1010101];
void bit_init(int n){bit_n=n;for(int i=0;i<=bit_n;i++)bit[i]=0;}
void add(int k){for(k++;k<=bit_n;k++)bit[k]++;}
void de(int k){for(k++;k<=bit_n;k++)bit[k]--;}
int sum(int k){int ret=0;for(k++;k;k-=k&-k)ret+=bit[k];return ret;}

int uf_n,par[1010101];
void uf_init(int n){uf_n=n;for(int i=0;i<uf_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)par[y]=x;}
bool same(int x,int y){return find(x)==find(y);}

vector<int>G[100000];
bool used[100000];

set<pair<int,int> >S;


int solve(vector<int>&vec){
    int ret=0;
    for(int i=0;i<vec.size();i++){
        ret+=i-sum(vec[i]-1);
        add(vec[i]);
    }
    for(int i=0;i<vec.size();i++)de(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_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(same(a,b))return -1;
        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;

    for(int i=0;i<N;i++){
        if(used[i]||G[i].size()!=1)continue;
        used[i]=true;
        vector<int>vec;
        vec.push_back(i);
        int v=G[i][0];
        int prev=i;
        while(G[v].size()!=1){
            int a=G[v][0],b=G[v][1];
            if(a==prev){
                vec.push_back(b);
                prev=v;
                v=b;
            }
            else{
                vec.push_back(a);
                prev=v;
                v=a;
            }
            used[v]=true;

        }
        vec.push_back(v);
        int v1=solve(vec);
        reverse(vec.begin(),vec.end());
        int v2=solve(vec);
        ans+=min(v1,v2);
    }

    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