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 ...