Submission #732534

#	Time	Username	Problem	Language	Result	Execution time	Memory
732534		Magikarp4000	Swapping Cities (APIO20_swap)	C++17	100 / 100	453 ms	46912 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 3e5+10, LOG = 21;
int n,m;
vector<int> v[MAXN];
vector<pair<int,PII>> e;
int p[MAXN], sz[MAXN], x[MAXN], deg[MAXN], p1[MAXN];
int jump[MAXN][LOG], depth[MAXN];
bool good[MAXN];
int cur;

int finds(int a) {
  if (p[a] != a) p[a] = finds(p[a]);
  return p[a];
}

void unite(int a, int b, int w) {
  int oa = a, ob = b;
  a = finds(a);
  b = finds(b);
  deg[oa]++; deg[ob]++;
  if (a != b) {
    p[a] = p[b] = p1[a] = p1[b] = cur;
    v[cur].PB(a);
    v[cur].PB(b);
    sz[cur] += sz[a]+sz[b];
    x[cur] = w;
    if (good[a] || good[b]) good[cur] = 1;
    if (deg[oa] >= 3 || deg[ob] >= 3) good[cur] = 1;
    cur++;
  }
  else {
    if (good[a]) return;
    good[a] = 1;
    x[a] = w;
  }
}

void dfs(int s, int pa) {
  FORX(u,v[s]) {
    if (u == pa) continue;
    depth[u] = depth[s]+1;
    dfs(u,s);
  }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a,b);
    FORR(j,LOG-1,-1) {
        if (jump[a][j] && depth[jump[a][j]] >= depth[b]) {
            a = jump[a][j];
        }
    }
    if (a == b && good[a]) return a;
    FORR(j,LOG-1,-1) {
        if (jump[a][j] != jump[b][j]) {
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    a = p1[a];
    if (good[a]) return a;
    FORR(j,LOG-1,-1) {
      if (jump[a][j] && !good[jump[a][j]]) a = jump[a][j];
    }
    a = p1[a];
    return a;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N; m = M;
  FOR(i,0,m) e.PB({W[i],{U[i]+1,V[i]+1}});
  sort(ALL(e));
  cur = n+1;
  FOR(i,1,MAXN) {
    p[i] = p1[i] = i;
    sz[i] = 1;
  }
  FORX(u,e) {
    unite(u.S.F, u.S.S, u.F);
  }
  dfs(cur-1,-1);
  FOR(i,1,cur) jump[i][0] = p1[i];
  FOR(j,1,LOG) {
    FOR(i,1,cur) jump[i][j] = jump[jump[i][j-1]][j-1];
  }
}

int getMinimumFuelCapacity(int a, int b) {
  a++; b++;
  int anc = lca(a,b);
  if (!good[anc]) return -1;
  return x[anc];
}

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