Submission #527800

---

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,int x){for(k++;k<=bit_n;k++)bit[k]+=x;}
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){
    vector<int>xs;
    for(int i=0;i<vec.size();i++)xs.push_back(vec[i]);
    sort(xs.begin(),xs.end());
    for(int i=0;i<vec.size();i++){
        vec[i]=lower_bound(xs.begin(),xs.end(),vec[i])-xs.begin();
    }

    int ret=LLONG_MAX/100;
    for(int Latte=0;Latte<2;Latte++){
        bit_init(xs.size());
        int val=0;
        for(int i=0;i<vec.size();i++){
            val+=i-sum(vec[i]-1);
            add(vec[i],1);
        }
        ret=min(ret,val);
        for(int i=0;i<vec.size();i++){
            vec[i]=xs.size()-1-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);
                v=b;
            }
            else{
                vec.push_back(a);
                v=a;
            }
            used[v]=true;
            prev=v;
        }
        vec.push_back(v);
        ans+=solve(vec);
    }

    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