Submission #472906

#	Time	Username	Problem	Language	Result	Execution time	Memory
472906		cs71107	Swapping Cities (APIO20_swap)	C++14	100 / 100	448 ms	56420 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;
typedef pair<int,int> pii;
const int MAXN = 1e5+10;

int pp[MAXN];
int id[MAXN];
int cal[MAXN];

int chk[MAXN*3];
int val[MAXN*3];
int ch[MAXN*3][3];

int vid[MAXN*3];
int depth[MAXN*3];
int par[MAXN*3][20];

vector<pii> edge[MAXN*2];

int root(int x){
    if(pp[x]==x)return x;
    else return pp[x] = root(pp[x]);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
        
  for(int i=0;i<N;i++){
    pp[i] = i;
    id[i] = i;
    ch[i][0] = -1;
    ch[i][1] = -1;
  }

  vector<int> pos = W;

  sort(pos.begin(),pos.end());
  pos.erase(unique(pos.begin(),pos.end()),pos.end());

  int sz = (int)pos.size();
  int idx = -1,idy = - 1;

  for(int i=0;i<M;i++){
    idx = lower_bound(pos.begin(),pos.end(),W[i])-pos.begin();
    edge[idx].push_back(pii(U[i],V[i]));
  }        

  int seq = N-1;
  int cur = 0;
  int x,y;
  int a,b;


  for(int i=0;i<sz;i++){
    cur = pos[i];
    for(int j=0;j<(int)edge[i].size();j++){
      x = edge[i][j].f;
      y = edge[i][j].s;

      cal[x]++;
      cal[y]++;

      a = root(x);
      b = root(y);

      idx = id[a];
      idy = id[b];

      seq++;

      if(a^b){
        pp[b] = a;
        id[a] = seq;

        chk[seq] = chk[idx]|chk[idy];
        
        if(cal[x]>=3||cal[y]>=3)chk[seq] = 1;

        val[seq] = cur;

        par[idx][0] = seq;
        par[idy][0] = seq;
        ch[seq][0] = idx;
        ch[seq][1] = idy;

      }
      else {
        id[a] = seq;
        chk[seq] = 1;
        val[seq] = cur;

        par[idx][0] = seq;
        ch[seq][0] = idx;
        ch[seq][1] = -1;
      }

    }

  }

  par[seq][0] = seq;
  
  vid[seq] = -1;

  for(int i=seq;i>=0;i--){
    if(chk[i])vid[i] = i;    

    if(ch[i][0]!=-1){
      vid[ch[i][0]] = vid[i];
      depth[ch[i][0]] = depth[i]+1;
    }
    if(ch[i][1]!=-1){
      vid[ch[i][1]] = vid[i];
      depth[ch[i][1]] = depth[i]+1; 
    }
  }

  for(int j=1;j<20;j++){
    for(int i=0;i<=seq;i++){
      par[i][j] = par[par[i][j-1]][j-1];
    }
  }

  /*
  for(int i=0;i<=seq;i++){
    cout<<i<<" "<<par[i][0]<<"\n";
    cout<<ch[i][0]<<" "<<ch[i][1]<<"\n";
    cout<<chk[i]<<" "<<val[i]<<" "<<vid[i]<<" "<<depth[i]<<"\n";
  }

  for(int i=0;i<=seq;i++){
    for(int j=0;j<=10;j++){
      cout<<par[i][j]<<" ";
    }
    cout<<"\n";
  }*/

  return;
}

int getMinimumFuelCapacity(int X, int Y) {
  
  if(depth[X]>depth[Y])swap(X,Y);

  int d = depth[Y]-depth[X];

  for(int i=19;~i;i--){
    if((1<<i)&d)Y = par[Y][i];
  }

  for(int i=19;~i;i--){
    if(par[X][i]^par[Y][i])X = par[X][i],Y = par[Y][i];
  }
  
  int lc = -1;

  if(X^Y)lc = par[X][0];
  else lc = X;

  //cout<<lc<<"\n";

  int ver = vid[lc];

  if(ver==-1)return -1;
  else return val[ver];
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27