Submission #508148

#	Time	Username	Problem	Language	Result	Execution time	Memory
508148		benson1029	Swapping Cities (APIO20_swap)	C++14	100 / 100	276 ms	43368 KiB

swap

#include "swap.h"

#include<bits/stdc++.h>
using namespace std;

int par[200005];
int lift[200005][20];
vector<int> krus[200005];
int st[200005], ed[200005];
int dsu[200005];
int ans[200005];
int deg[200005];
int timer = 0;
pair< int, pair< int, int> > edg[200005];

bool anc(int x, int y) {
  return st[x] <= st[y] && ed[x] >= ed[y];
}

int lca(int x, int y) {
  if(anc(x, y)) return x;
  for(int i=19; i>=0; i--) {
    if(lift[x][i]==-1) continue;
    if(!anc(lift[x][i], y)) x = lift[x][i];
  }
  return lift[x][0];
}

int find(int x) {
  if(dsu[x]==x) return x;
  else return dsu[x] = find(dsu[x]);
}

void dfs(int x) {
  st[x] = ++timer;
  lift[x][0] = par[x];
  for(int i=1; i<20; i++) {
    if(lift[x][i-1]==-1) lift[x][i]=-1;
    else lift[x][i] = lift[lift[x][i-1]][i-1];
  }
  for(int i:krus[x]) {
    ans[i] = min(ans[i], ans[x]);
    dfs(i);
  }
  ed[x] = ++timer;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    for(int i=0; i<M; i++) {
      edg[i] = {W[i], {U[i], V[i]} };
    }
    sort(edg, edg+M);
    for(int i=0; i<N*2; i++) dsu[i] = i, ans[i] = 2e9, deg[i] = 0;
    int tmp = N;
    for(int i=0; i<M; i++) {
      if(find(edg[i].second.first) != find(edg[i].second.second)) {
        krus[tmp].push_back(dsu[edg[i].second.first]);
        krus[tmp].push_back(dsu[edg[i].second.second]);
        par[dsu[edg[i].second.first]] = par[dsu[edg[i].second.second]] = tmp;
        if(ans[dsu[edg[i].second.first]]<2e9 || ans[dsu[edg[i].second.second]]<2e9) ans[tmp] = edg[i].first;
        dsu[dsu[edg[i].second.first]] = dsu[dsu[edg[i].second.second]] = tmp;
        tmp++;
      } else { // cycle
        ans[find(edg[i].second.first)] = min(ans[find(edg[i].second.first)], edg[i].first);
      }
      deg[edg[i].second.first]++; deg[edg[i].second.second]++;
      if(deg[edg[i].second.first] >= 3 || deg[edg[i].second.second] >= 3) {
        ans[find(edg[i].second.first)] = min(ans[find(edg[i].second.first)], edg[i].first);
      }
    }
    par[tmp-1] = -1;
    dfs(tmp-1);
}

int getMinimumFuelCapacity(int X, int Y) {
  return ans[lca(X, Y)] == 2e9 ? -1 : ans[lca(X, Y)];
}

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