Submission #2518920
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
Submission Time | |
---|---|
Task | A - 国際道迷いオリンピック(International Michimayoi Olympic) |
User | luogu_bot1 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 2848 Byte |
Status | CE |
Compile Error
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 0 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 1 has invalid symbol index 12 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 2 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 3 has invalid symbol index 2 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 4 has invalid symbol index 11 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 5 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 6 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 7 has invalid symbol index 13 /usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 8 has invalid symbol ...