Submission #527770
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; void init(int _n){ n=_n; par.clear(); par.resize(n); 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)par[y]=x; } bool same(int x,int y){ return find(x)==find(y); } }; vector<int>G[100000]; bool used[100000]; 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(int N, int M,int 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(uf.same(a,b))return -1; uf.unite(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); for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";cout<<endl; 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
Submission Time | |
---|---|
Task | A - 国際道迷いオリンピック(International Michimayoi Olympic) |
User | latte0119 |
Language | IOI-Style C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 3003 Byte |
Status | CE |
Compile Error
/tmp/ccLVpY9s.o: In function `main': grader.cpp:(.text+0x0): multiple definition of `main' /tmp/ccJpO6Yt.o:Main.cpp:(.text+0xd50): first defined here /tmp/ccLVpY9s.o: In function `main': grader.cpp:(.text+0x8c): undefined reference to `best_swap(int, int, int (*) [2])' collect2: ld returned 1 exit status