Submission #2515028

---

Source Code Expand

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <queue>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;

class UnionFind{
  int n;
  vector<int> data;
public:
  UnionFind(int _n):n(_n),data(_n,-1){}
  bool link(int a, int b){ //if new link, then true.
    int ra=find_root(a);
    int rb=find_root(b);
    if(ra!=rb){
      if(data[rb]<data[ra]) swap(ra,rb);
      data[ra]+=data[rb];
      data[rb]=ra;
    }
    return (ra!=rb);
  }
  bool check(int a, int b){ //if same set, then true.
    return (find_root(a)==find_root(b));
  }
  int find_root(int a){
    return ((data[a]<0)?a:(data[a]=find_root(data[a])));
  }
};

ll mergecount(vector<int> &a) {
  ll count = 0;
  ll n = a.size();
  if (n > 1) {
    vector<int> b(a.begin(), a.begin() + n/2);
    vector<int> c(a.begin() + n/2, a.end());
    count += mergecount(b);
    count += mergecount(c);
    for (int i = 0, j = 0, k = 0; i < n; ++i)
      if (k == c.size())       a[i] = b[j++];
      else if (j == b.size())  a[i] = c[k++];
      else if (b[j] <= c[k])   a[i] = b[j++];
      else                   { a[i] = c[k++]; count += n/2 - j; }
  }
  return count;
}


map<pair<int,int>,int> memo;
vector<int> G[100005];
vector<int> GROUP[100005];
ll ret;

ll solve(int N, int idx){
  if(GROUP[idx].size()<=2) return 0;

  vector<int> walk;
  map<int,int> visited;

  bool flg = false;
  rep(i,GROUP[idx].size()){
    if(G[GROUP[idx][i]].size()==1){ //端点
      int prev = -1;
      int st = GROUP[idx][i];
      while(true){
        walk.push_back(st);
        visited[st] = 1;
  
        int nx = -1;
        rep(j, G[st].size()){
          if(G[st][j] == prev) continue;
          if(visited[G[st][j]] == 1) return -1;
          nx = G[st][j];
        }
        if(nx == -1) break;
        prev = st;
        st = nx;
      }
      flg = true;
      break;
    }
  }

  if(!flg) return -1;
  
  //rep(i,walk.size()) cerr << walk[i] << " "; cerr << endl;

  //walkの昇順または降順でバブルソートswap回数が少ないほうを返す
  vector<int> walk_tmp = walk;
  ll a = mergecount(walk_tmp);
  reverse(ALLOF(walk));
  ll b = mergecount(walk);
  
  return min(a,b);
}

long long best_swap(int N, int M,int E[][2]){

  int real_M = 0;
  UnionFind uf(N);
  rep(i,M){
    if(memo[make_pair(E[i][0],E[i][1])]==1) continue;
    memo[make_pair(E[i][0],E[i][1])]=1;
    memo[make_pair(E[i][1],E[i][0])]=1;
    real_M++;
    
    G[E[i][0]].push_back(E[i][1]);
    G[E[i][1]].push_back(E[i][0]);
    //頂点につながる辺の本数が2本より多い
    if(G[E[i][0]].size()>2) return -1;
    if(G[E[i][1]].size()>2) return -1;
    
    uf.link(E[i][0], E[i][1]);
  }

  if(N<=real_M) return -1; //必ずサイクルができる
  
  //連結成分ごとにまとめる
  rep(i,N){
    GROUP[uf.find_root(i)].push_back(i);
  }

  ret = 0;

  //各連結成分について、最小swap回数を求める
  rep(i,N){
    ll res = solve(N, i);
    if(res < 0) return -1; //サイクルがあった
    ret += res;
  }
  
  return ret;
}

Submission Info

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