Submission #1198907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198907		hengliao	Swapping Cities (APIO20_swap)	C++20	100 / 100	260 ms	71100 KiB

swap

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

#define F first 
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll; // warning

namespace{
  const ll mxN=2e5+5;
  const ll inf=1e18;
  const ll LOG=20;

  struct edge{
    ll u, v, w;

    bool operator<(const edge &tar) const{
      return w<tar.w;
    }
  };
  ll n, m;
  vll adj[mxN];
  vector<pll> adj2[mxN]; 
  ll deg[mxN];
  bool visited[mxN];
  ll dumb[mxN];
  ll oth[mxN];
  vector<edge> edges;
  ll dsu[mxN];
  ll p[mxN], d[mxN];
  ll up[mxN][LOG];
  ll up2[mxN][LOG];

  ll find_set(ll tar){
    if(dsu[tar]<0) return tar;
    return dsu[tar]=find_set(dsu[tar]);
  }

  void unite(ll a, ll b){
    ll f=find_set(a);
    ll s=find_set(b);
    if(abs(dsu[f])<abs(dsu[s])) swap(f, s);
    dsu[f]+=dsu[s];
    dsu[s]=f;
  }

  void dfs(ll cur, ll w){
    if(visited[cur]) return;
    visited[cur]=1;
    dumb[cur]=w;
    for(auto &it:adj[cur]){
      dfs(it, w);
    }
  }

  void dfs2(ll cur, ll par, ll dep, ll w){
    p[cur]=par;
    up[cur][0]=par;
    up2[cur][0]=w;
    d[cur]=dep;
    for(auto &[chd, ww]:adj2[cur]){
      if(chd==par) continue;
      dfs2(chd, cur, dep+1, ww);
    }
  } 

  pll kth(ll tar, ll k){
    ll re=0;
    for(ll i=0;i<LOG;i++){
      if(k&(1LL<<i)){
        re=max(re, up2[tar][i]);
        tar=up[tar][i];
      }
    }
    return {tar, re};
  }

  pll lca(ll a, ll b){
    if(d[a]>d[b]) swap(a, b);
    ll re=0;
    pll tep=kth(b, d[b]-d[a]);
    re=tep.S;
    b=tep.F;
    if(a==b){
      return {a, re};
    }
    for(ll i=LOG-1;i>=0;i--){
      if(up[a][i]!=up[b][i]){
        re=max(re, up2[a][i]);
        re=max(re, up2[b][i]);
        a=up[a][i];
        b=up[b][i];
      }
    }
    re=max(re, up2[a][0]);
    re=max(re, up2[b][0]);
    return {up[a][0], re};
  }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n=N;
  m=M;
  memset(deg, 0, sizeof(deg));
  memset(visited, 0, sizeof(visited));
  memset(dsu, -1, sizeof(dsu));
  for(ll i=0;i<n;i++){
    dumb[i]=inf;
  }
  for(ll i=0;i<m;i++){
    edges.pb({U[i], V[i], W[i]});
  }
  sort(edges.begin(), edges.end());
  for(auto &it:edges){
    adj[it.u].pb(it.v);
    adj[it.v].pb(it.u);
    deg[it.u]++;
    deg[it.v]++;
    if(visited[it.u] || visited[it.v]){
      dfs(it.u, it.w);
      dfs(it.v, it.w);
    }
    else{
      if(deg[it.u]>2 || deg[it.v]>2){
        dfs(it.u, it.w);
        dfs(it.v, it.w);
      }
      else if(deg[it.u]==2 && deg[it.v]==2){
        if(oth[it.u]==it.v){
          dfs(it.u, it.w);
          dfs(it.v, it.w);
        }
        else{
          ll f=oth[it.u];
          ll s=oth[it.v];
          oth[f]=s;
          oth[s]=f;
        }
      }
      else if(deg[it.u]==2){
        ll f=oth[it.u];
        oth[f]=it.v;
        oth[it.v]=f;
      }
      else if(deg[it.v]==2){
        ll f=oth[it.v];
        oth[f]=it.u;
        oth[it.u]=f;
      }
      else{
        oth[it.u]=it.v;
        oth[it.v]=it.u;
      }
    }
  }
  for(auto &it:edges){
    if(find_set(it.u)!=find_set(it.v)){
      adj2[it.u].pb({it.v, it.w});
      adj2[it.v].pb({it.u, it.w});
      unite(it.u, it.v);
    }
  }
  dfs2(0, 0, 0, 0);
  for(ll j=1;j<LOG;j++){
    for(ll i=0;i<n;i++){
      up[i][j]=up[up[i][j-1]][j-1];
      up2[i][j]=max(up2[i][j-1], up2[up[i][j-1]][j-1]);
    }
  }
}

int getMinimumFuelCapacity(int x, int y) {
  ll ans=max(dumb[x], dumb[y]);
  ans=max(ans, lca(x, y).S);
  if(ans==inf){
    return -1;
  }
  return (int) ans;
}

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