Submission #527784

---

Source Code Expand

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

struct BIT{
    int n;
    vector<int>dat;
    void init(int _n){
        n=_n;
        dat.clear();
        dat.resize(n+1,0);
    }
    void add(int k,int x){
        for(k++;k<=n;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};

struct UF{
    int n;
    vector<int>par,sz;
    void init(int _n){
        n=_n;
        par.clear();
        sz.clear();
        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];

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();
    }

    BIT bit;

    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++){
            int v=bit.sum(vec[i]-1);
            val+=i-v;
            //cout<<"**"<<i-v<<endl;
            bit.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 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))))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;

    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;
        }
        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

Compile Error

./Main.cpp: In function ‘long long int best_swap(int, int, int (*)[2])’:
./Main.cpp:98: error: could not convert ‘S.std::set<_Key, _Compare, _Alloc>::find [with _Key = std::pair<long long int, long long int>, _Compare = std::less<std::pair<long long int, long long int> >, _Alloc = std::allocator<std::pair<long long int, long long int> >](((const std::pair<long long int, long long int>&)((const std::pair<long long int, long long int>*)(& std::pair<long long int, long long int>(((const long long int&)((const long long int*)std::min [with _Tp = long long int](((const long long int&)((const long long int*)(& a))), ((const long long int&)((const long long int*)(& b)))))), ((const long long int&)((const long long int*)std::max [with _Tp = long long int](((const long long int&)((const long long int*)(& a))), ((const long long int&)((const long long int*)(& b)))))))))))’ to ‘bool’