Submission #1202132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202132		ackhava	Swapping Cities (APIO20_swap)	C++20	100 / 100	284 ms	57532 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(v) begin(v), end(v)
#define REP(i,o,n) for(int i=o;i<n;i++)
using namespace std;
#include <vector>

int depth[400500];

struct dsu {
  vector<int> vec;
  vector<int> lead;
  vector<pair<int,bool>> info;

  dsu(int n=0){
    vec.clear();
    vec.resize(n+10,-1);
    lead.clear();
    lead.resize(n+10,-1);
    info.clear();
    info.resize(n+10,{0,false});
  }

  void init(int n=0){
    vec.clear();
    vec.resize(n+10,-1);
    lead.clear();
    lead.resize(n+10,-1);
    info.clear();
    info.resize(n+10,{0,false});
  }

  int depth(int n){
    if(::depth[n]!=-1)return ::depth[n];
    if(vec[n]==-1)return ::depth[n]=0;
    return ::depth[n]=depth(vec[n])+1;
  }

  int leader(int n){
    return lead[n]<0?n:lead[n]=leader(lead[n]);
  }

  void merge(int u, int v, int w, bool has_three){
    u=leader(u),v=leader(v);
    int idx=vec.size();
    vec.pb(-1);
    lead.pb(-1);
    info.pb({w,has_three});
    vec[u]=lead[u]=vec[v]=lead[v]=idx;
    info[idx].se=info[idx].se || info[u].se || info[v].se || (u==v);
  }
};

dsu d;
vector<int> aw[200100];
int lift[400500][20];

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  memset(depth,-1,sizeof depth);
  d.init(N);
  vector<pair<int,pair<int,int>>> vec;
  REP(i,0,M){
    vec.pb({W[i],{U[i],V[i]}});
  }
  sort(all(vec));
  for(auto i:vec){
    aw[i.se.fi].pb(i.fi);
    aw[i.se.se].pb(i.fi);
    d.merge(i.se.fi,i.se.se,i.fi,aw[i.se.fi].size()>=3 || aw[i.se.se].size() >= 3);
  }
  REP(i,0,d.vec.size())depth[i]=d.depth(i);
  memset(lift,-1,sizeof lift);
  REP(i,0,d.vec.size()){
    lift[i][0]=d.vec[i];
  }
  REP(j,1,20){
    REP(i,0,d.vec.size()){
      if(lift[i][j-1]!=-1)lift[i][j]=lift[lift[i][j-1]][j-1];
    }
  }
  REP(i,0,N+10){
    sort(all(aw[i]));
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  int x=X,y=Y;
  REP(ix,0,20){
    auto i=20-1-ix;
    if(lift[X][i] != -1 && depth[lift[X][i]]>=depth[Y])X=lift[X][i];
  }
  swap(X,Y);
  REP(ix,0,20){
    auto i=20-1-ix;
    if(lift[X][i] != -1 && depth[lift[X][i]]>=depth[Y])X=lift[X][i];
  }
  REP(ix,0,20){
    auto i=20-1-ix;
    if(lift[X][i]!=lift[Y][i] && lift[X][i]!=-1 && lift[Y][i]!=-1)X=lift[X][i],Y=lift[Y][i];
  }
  while(X!=Y && lift[X][0]!=-1 && lift[Y][0]!=-1){
    X=lift[X][0];
    Y=lift[Y][0];
  }
  if(X!=Y)return -1;
  int base=d.info[X].fi;
  int ext=2e9;
  // if(aw[x].size()>1)ext=min(ext,aw[x][1]);
  // if(aw[y].size()>1)ext=min(ext,aw[y][1]);
    REP(ix,0,20){
    auto i=20-1-ix;
    if(lift[X][i]!=-1 && !d.info[lift[X][i]].se)X=lift[X][i],Y=lift[Y][i];
  }
  while(lift[X][0]!=-1 && !d.info[X].se)X=lift[X][0];
  if(d.info[X].se)ext=min(ext,d.info[X].fi);
  return (ext>1e9)?-1:max(ext,base);
}

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