Submission #1180373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180373		meisgood	Swapping Cities (APIO20_swap)	C++20	100 / 100	588 ms	99640 KiB

swap

#include "swap.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std ;
#define aaa 400003
// #define aaa 203
int n,m ;
int gp[aaa] ;
vector <int> gps[aaa] ;
int ok[aaa] ;
int dsu(int x){
  if (x==gp[x]) return x ;
  gp[x]=dsu(gp[x]) ;
  return gp[x] ;
}
void un(int a,int b,int nw){
  a=dsu(a),b=dsu(b) ;
  if (a==b){
    if (ok[a]==INT_MAX) for (auto x : gps[a]) ok[x]=nw ;
    return ;
  }
  if (gps[a].size()<gps[b].size()) swap(a,b) ;
  for (auto x : gps[b]) gps[a].push_back(x) ;
  gps[b].clear() ;
  gp[dsu(b)]=dsu(a) ;
}
int gp2[aaa] ;
int dsu2(int x){
  if (x==gp2[x]) return x ;
  gp2[x]=dsu2(gp2[x]) ;
  return gp2[x] ;
}
int anc[32][aaa] ;
int dep[aaa] ;
int ww[aaa] ;
vector <int> adj2[aaa] ;
void dfs(int x){
  for (auto a : adj2[x]) dep[a]=dep[x]+1,dfs(a) ;
}
int lca(int u,int v){
  if (dep[u]<dep[v]) swap(u,v) ;
  for (int k = 31 ; k >= 0 ; k --){
    if (dep[anc[k][u]]>=dep[v]) u=anc[k][u] ;
  }
  if (u==v) return u ;
  for (int k = 31 ; k >= 0 ; k --){
    if (anc[k][u]!=anc[k][v]) u=anc[k][u],v=anc[k][v] ;
  }
  return anc[0][u] ;
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n=N,m=M ;
  int i,j ;
  map <int,vector<pair<int,int>>> mp ;
  vector <int> adj[aaa] ;
  for (i = 0 ; i < n ; i ++) ok[i]=INT_MAX,gp[i]=i,gps[i].push_back(i) ;
  for (i = 0 ; i < m ; i ++){
    mp[W[i]].push_back({U[i],V[i]}) ;
    // mp[W[i]].push_back({V[i],U[i]}) ;
  }
  for (auto [x,v] : mp){
    for (auto [a,b] : v){
      adj[a].push_back(b) ;
      adj[b].push_back(a) ;
      if (ok[a]!=INT_MAX&&ok[b]==INT_MAX) for (auto aa : gps[dsu(b)]) ok[aa]=x ;
      if (ok[b]!=INT_MAX&&ok[a]==INT_MAX) for (auto aa : gps[dsu(a)]) ok[aa]=x ;
      un(a,b,x) ;
      if (adj[a].size()>=3){
        if (ok[a]==INT_MAX){
          for (auto aa : gps[dsu(a)]) ok[aa]=x ;
        }
      }
      if (adj[b].size()>=3){
        if (ok[b]==INT_MAX){
          for (auto aa : gps[dsu(b)]) ok[aa]=x ;
        }
      }
    }
  }
  // for (i = 0 ; i < n ; i ++) cout << ok[i] << " " ; cout << endl ;
  for (i = 0 ; i < n+m ; i ++) gp2[i]=i ;
  vector <pair<int,pair<int,int>>> adjj ;
  for (i = 0 ; i < m ; i ++) adjj.push_back({W[i],{U[i],V[i]}}) ;
  sort(adjj.begin(),adjj.end()) ;
  int cnt=n ;
  for (auto [w,abc] : adjj){
    auto [a,b]=abc ;
    if (dsu2(a)==dsu2(b)) continue ;
    a=dsu2(a),b=dsu2(b) ;
    gp2[a]=cnt,gp2[b]=cnt ;
    anc[0][a]=cnt,anc[0][b]=cnt ;
    adj2[cnt].push_back(a) ;
    adj2[cnt].push_back(b) ;
    ww[cnt]=w ;
    anc[0][cnt]=cnt ;
    cnt++ ;
  }
  dep[cnt-1]=0 ;
  dfs(cnt-1) ;
  for (int k = 1 ; k < 32 ; k ++){
    for (i = 0 ; i < cnt ; i ++){
      anc[k][i]=anc[k-1][anc[k-1][i]] ;
    }
  }
  // cout << ww[lca(1,3)] << endl ;
}

int getMinimumFuelCapacity(int X, int Y) {
  int mx=-1 ;
  mx=max(mx,ok[X]) ;
  mx=max(mx,ok[Y]) ;
  mx=max(mx,ww[lca(X,Y)]) ;
  if (mx==INT_MAX) mx=-1 ;
  return mx;
}

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