Submission #567604

#	Time	Username	Problem	Language	Result	Execution time	Memory
567604		farhan132	Swapping Cities (APIO20_swap)	C++17	100 / 100	862 ms	94176 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 3e5 + 15;

ll par[N], ok[N], n, val[N], pr[20][N];
ii p[N];
vector < ll > v[N];

ll find(ll a){
  if(a == par[a]) return a;
  return par[a] = find(par[a]);
}
ll eq(ii x, ii y){
  if(x == y || x == make_pair(y.ss, y.ff)) return 1;
  return 0; 
}
void merge(ll x, ll y, ll ww){
  ii w = {x, y};

  x = find(x);

  y = find(y);

  ++n;
  val[n] = ww;
  ok[n] = (ok[x] & ok[y]);


  par[x] = par[y] = n;
  par[n] = n;
  v[n].pb(x);
  if(x != y) v[n].pb(y);
  
  if(ok[n]){
    if(x == y){
      ok[n] = 0;
    }else{
      bool f = 0;
      ii wut;
      for(auto z1 : {p[x].ff, p[x].ss}){
        for(auto z2 : {p[y].ff, p[y].ss}){
          if(eq(w, {z1, z2})) f = 1, wut = {z1, z2};
        }
      }
      if(!f){
        ok[n] = 0;
      }else{
        if(wut.ff == p[x].ff) p[n].ff = p[x].ss;
        else p[n].ff = p[x].ff;
        if(wut.ss == p[y].ff) p[n].ss = p[y].ss;
        else p[n].ss = p[y].ff;
      }
    }
  }
  
  return;
}
ll d[N];
void dfs(ll s, ll _p, ll dp){
  pr[0][s] = _p;
  d[s] = dp;
  for(ll i = 1; i < 20; i++) pr[i][s] = pr[i-1][pr[i-1][s]];
  for(auto u : v[s]){
    dfs(u, s, dp + 1);
  }
  return;
}
ll lca(ll x, ll y){
  if(d[x] < d[y]) swap(x, y);
  for(ll i = 19; i >= 0; i--){
    if(d[x] - (1 << i) >= d[y]) x = pr[i][x];
  }
  if(x == y) return x;
  for(ll i = 19; i >= 0; i--){
    if(pr[i][x] == pr[i][y]) continue;
    x = pr[i][x], y = pr[i][y];
  }
  return pr[0][x];
}

void init(int _n, int m, vector<int> U, vector<int> V, vector<int> W) {
  n = _n;
  vector < tuple < ll , ll , ll > > e;
  for(ll i = 0; i < m; i++) e.pb({W[i], V[i]+1, U[i]+1});
  for(ll i = 1; i <= n; i++){
    par[i] = i;
    p[i] = {i, i};
    ok[i] = 1;
  }

  sort(e.begin(), e.end());
  for(auto [w, x, y] : e){
    merge(x, y, w);
  }
  dfs(n, n, 1);
  return;
}

int getMinimumFuelCapacity(int x, int y) {
  x++; y++;
  if(ok[n] == 1) return -1;

  ll cur = lca(x, y);
  if(!ok[cur]) return val[cur];
  for(ll i = 19; i >= 0; i--){
    if(!ok[pr[i][cur]]) continue;
    cur = pr[i][cur];
  }
  cur = pr[0][cur];
  return val[cur];
}

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