Submission #1185583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185583		loom	Swapping Cities (APIO20_swap)	C++20	100 / 100	259 ms	54064 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 2e9

const int N = 1e5, N3 = 3*N;
vector<int> g[N3];
int swp[N], p[N], sz[N], deg[N], ix[N];
int dep[N], tswp[N3], lswp[N3], wt[N3], up[N3][19];

int find(int x){
   return x == p[x] ? x : p[x] = find(p[x]);
}

int unite(int x, int y){
   int px = find(x);
   int py = find(y);
   if(sz[px] < sz[py]) swap(px, py);

   if(px == py){
      swp[px] = 1;
      return px;
   }

   deg[x]++;
   deg[y]++;
   if(max(deg[x], deg[y]) >= 3) swp[px] = 1;
   if(swp[px] or swp[py]) swp[px] = 1;

   p[py] = px;
   sz[px] += sz[py];
   return px;
}

void dfs(int v, int l){
   if(tswp[v]) l = v;
   lswp[v] = l;

   for(int ch : g[v]){
      dep[ch] = dep[v]+1;
      dfs(ch, l);
   }
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
   vector<tuple<int,int,int>> ed(m);
   for(int i=0; i<m; i++){
      ed[i] = {w[i], u[i], v[i]};
   }
   sort(ed.begin(), ed.end());

   iota(p, p+n, 0);
   iota(ix, ix+n, 0);
   up[m-1+n][0] = -1;

   for(int i=0; i<m; i++){
      auto [w, a, b] = ed[i];

      int pa = find(a);
      int pb = find(b);

      g[i+n].push_back(ix[pa]);
      up[ix[pa]][0] = i+n;
      if(pa != pb){
         g[i+n].push_back(ix[pb]);
         up[ix[pb]][0] = i+n;
      }

      int pr = unite(a, b);
      tswp[i+n] = swp[pr];
      wt[i+n] = w;
      ix[pr] = i+n;
   }

   for(int j=1; j<19; j++){
      for(int i=0; i<m+n; i++) up[i][j] = (up[i][j-1] == -1 ? -1 : up[up[i][j-1]][j-1]);
   }

   dep[m-1+n] = 0;
   dfs(m-1+n, -1);
}

int getMinimumFuelCapacity(int a, int b){
   if(dep[a] > dep[b]) swap(a, b);
   int d = dep[b] - dep[a];

   for(int i=0; i<19; i++) if(d & (1<<i)) b = up[b][i];
   for(int i=18; i>=0; i--) if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];

   if(a != b) a = up[a][0];
   return (lswp[a] == -1 ? -1 : wt[lswp[a]]);
}

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