Submission #2546849
Source Code Expand
#include <cstdio> #include <cstdlib> #include <numeric> #include <cstring> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <cassert> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <iomanip> #include<sys/time.h> using namespace std; double e_time(void){static struct timeval now;gettimeofday(&now, NULL);return (double)(now.tv_sec + now.tv_usec/1000000.0);} #define REP(i,b,n) for(int i=b;i<n;i++) #define rep(i,n) REP(i,0,n) #define pb push_back #define mp make_pair #define ALL(C) (C).begin(),(C).end() #define fe(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr != (c).end();itr++) #define BITSHIFT(X) ( (1<<(X)) ) #define CONTAIN(S,X) ( ((S)&BITSHIFT(X)) != 0) typedef complex<double>P; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef vector<int> vint; template<class T> void vp(T &a,int p){rep(i,p)cout << a[i]<<" ";cout << endl;} template<class T> T ceilUp(const T& a,const T& b){return (a+b-1)/b;} const ll mod = 1000000009; inline ll modadd(ll a,ll b){a %= mod;b %= mod;return (a+b)%mod;} inline ll modsub(ll a,ll b){a %= mod;b %= mod;a-=b;a%=mod;if (a<0)a+=mod;return a;} inline ll modmul(ll a,ll b){a %= mod;b %= mod;return (a*b)%mod;} const int MAX=100010; long long count; int L[MAX],R[MAX]; int in[MAX],in2[MAX]; vector<int> edge[MAX]; class DisjointSet{ public: vector<int> rank,p; DisjointSet(){} DisjointSet(int size){ rank.resize(size,0); p.resize(size,0); } void make_set(int x){ p[x]=x; rank[x]=0; } void merge(int x,int y){ link(find_set(x),find_set(y)); } void link(int x,int y){ if (rank[x]>rank[y]){ p[y]=x; }else { p[x]=y; if ( rank[x] ==rank[y])rank[y]+=1; } } int find_set(int x){ if (x != p[x])p[x]=find_set(p[x]); return p[x]; } }; void Merge(int a[],int l,int mid,int r){ int n1 = mid - l+1,n2 = r-mid; for(int i=0;i<n1;i++){ L[i]=a[l+i]; } for(int i=0;i<n2;i++){ R[i]=a[mid+i+1]; } L[n1]=R[n2]=INT_MAX; int pr =0,pl = 0; for(int i=l;i<r+1;i++){ if ( L[pl] <= R[pr]){ a[i]=L[pl++]; } else if (L[pl]>R[pr]){ ::count+=n1-pl; //cout << R[pr] << endl; a[i]=R[pr++]; } } } void MergeSort(int a[],int l,int r){ if (l < r){ int q = (r+l)/2; MergeSort(a,l,q); MergeSort(a,q+1,r); Merge(a,l,q,r); } } //loop finding int vis[MAX]; bool loopFindingDfs(int u,int prev){ if (vis[u] == 2)return false; if (vis[u] == 1)return true; vis[u]=1; rep(i,(int)edge[u].size()){ if (prev == edge[u][i])continue; if (loopFindingDfs(edge[u][i],u))return true; } vis[u]=2; return false; } bool hasLoop(int n){ rep(i,n)vis[i]=0; rep(i,n){ if (vis[i] == 0 && loopFindingDfs(i,-1)){ return true; } } return false; } //loop finding end int deg[MAX]; bool visited[MAX]; int dfs(int *in,int p,int cur,int prev){ int deg2 = 0; int deg1 = 0; while(true){ bool fg = false; visited[cur] = true; in[p++] = cur; if (edge[cur].size() >= 3)return -1; if (edge[cur].size() == 2)deg2++; if (edge[cur].size() == 1)deg1++; rep(i,edge[cur].size()){ int next = edge[cur][i]; if (next == prev)continue; fg = true; prev = cur; cur = next; break; } if (!fg)break; } if (deg1 > 2 )return -1; return p; } ll f3(int N){ ll ans = 0; rep(i,N)visited[i] = false; rep(i,N){ if (deg[i] == 1 && !visited[i]){ int index = dfs(in,0,i,-1); if (index == -1)return -1; if (index <= 2)continue;//孤立点,やばそうだから無視する rep(i,index)in2[i] = in[i]; reverse(in2,in2+index); ll tmp = LONG_LONG_MAX; ::count = 0; MergeSort(in,0,index-1); tmp = min(tmp,::count); ::count = 0; MergeSort(in2,0,index-1); tmp = min(tmp,::count); ans += tmp; } } return ans; } long long best_swap(int N, int M,int E[][2]){ rep(i,N)deg[i] = 0,edge[i].clear(); vector<pair<int,int> > all; rep(i,M){ if (E[i][0] > E[i][1])swap(E[i][0],E[i][1]); all.push_back(make_pair(E[i][0],E[i][1])); } sort(ALL(all)); all.erase(unique(ALL(all)),all.end()); rep(i,all.size()){ int f = all[i].first,s = all[i].second; deg[f]++; deg[s]++; edge[f].push_back(s); edge[s].push_back(f); } if (hasLoop(N)){ return -1; } return f3(N); }
Submission Info
Submission Time | |
---|---|
Task | A - 国際道迷いオリンピック(International Michimayoi Olympic) |
User | luogu_bot2 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 4832 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 ...