Submission #966828

#	Time	Username	Problem	Language	Result	Execution time	Memory
966828		AlperenT_	Swapping Cities (APIO20_swap)	C++14	6 / 100	397 ms	76644 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ll long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10 + 10,  inf = 1e9+10 , mod = 1e9 + 7 , lg = 20 ;
int cnt = 1 , par[maxn] , dis[maxn] , mark[maxn] , p[maxn][lg+1] , mn[maxn][lg+1]  , mn2[maxn][lg+1] ;
vector <pii> T[maxn] ;
vector <pii> G[maxn];  
set <pii> s[maxn] ;

int find(int v){
  if(par[v]==0)return v;
  return par[v] = find(par[v]) ;
}

void bui(int v , int r =0 ){
  p[v][0] = r;mark[v] = 1;
  rep(i , 1 ,lg)p[v][i] = p[p[v][i-1]][i-1] ; 
  for(auto [w,u] : T[v]){
    if(u == r)continue ;
    bui(u,v);
  }
}

vector<int> tp;
void dfs(int v, int r =0){
  mark[v] =1 ;
  tp.pb(v);
  for(auto [w,u] : T[v]){
    if(r == u)continue ;
    dis[u] = dis[v] + 1;
    mn2[u][0] = w;
    dfs(u , v) ;
    if(sz(s[u]) > sz(s[v]))swap(s[v],s[u]);
    while(sz(s[u])){
      s[v].insert(*s[u].begin());
      s[u].erase(s[u].begin()); 
    }
  }
  for(auto [w,u] : G[v]){
    if(dis[u] < dis[v]){
      s[v].insert({w,u}) ;
    }
  }
  mn[v][0] = inf ;
  while(sz(s[v])){
    int u =(*s[v].begin()).S , w = (*s[v].begin()).F ;
    if(dis[v]<=dis[u]){
      s[v].erase(s[v].begin());
      continue ;
    }
    mn[v][0] = w ;
    break ;
  }
}

pii up(int v ,int d){
    int r = inf , r2 = 0;
    rep(i , 0  ,lg)if(d>>i&1){
      r = min(r , mn[v][i]) ;
      r2= max(r2 , mn2[v][i]) ;
      v = p[v][i] ;
    }
    return (pii){r,r2};
}
int up2(int v ,int d){
     rep(i , 0  ,lg)if(d>>i&1){
      v = p[v][i] ;
    }
    return v; 
}
int lca2(int v, int u){
  if(dis[v] < dis[u])swap(v,u);
  v = up2(v ,dis[v]-dis[u]) ;
  per(i , lg , 0){
    if(p[v][i] != p[u][i]){
      v = p[v][i] ;
      u = p[u][i] ;
    }
  }
  if(v==u)return v ;
  return p[v][0] ;
}
int lca(int v, int u){
  if(dis[v] < dis[u])swap(v,u);
  pii a = up(v , dis[v]-dis[u]) ;
  v = up2(v,dis[v]-dis[u]) ;
  int a1 = a.F ,a2 =a.S; 
  per(i , lg , 0){
    if(p[v][i] != p[u][i]){
      a1 = min({a1 ,mn[v][i] , mn[u][i]});
      a2 = max({a2 ,mn2[v][i] , mn2[u][i]}) ;
      v = p[v][i] ;
      u = p[u][i] ;
    }
  }
  if(v==u)return max(a1 ,a2)  ;
  a1 = min({a1 ,mn[v][0] , mn[u][0]});
  a2 = max({a2 ,mn2[v][0] , mn2[u][0]}) ;
  return max(a1 ,a2);
}
int id[maxn] ;
void init(int n, int m,vector<int>U, vector<int> V, vector<int> W) {
  vector<pair<int,pii> > ed;
  rep(i , 0 , m-1){
    V[i]++;U[i]++;
    ed.pb({W[i] , {V[i],U[i]}});
  }
  sort(all(ed));
  rep(i , 0 ,sz(ed)-1){
    int v = ed[i].S.F, u = ed[i].S.S , w = ed[i].F ;
    if(find(v) == find(u)){
      id[i] = 1 ;
    }else{
      par[find(v)] = find(u);
      T[v].pb({w,u});
      T[u].pb({w,v}); 
    }
  }
  rep(i ,1 , n){
    if(mark[i] == 1)continue ;
    bui(i) ;
  }
  rep(i ,1 ,n)mark[i] =0 ;
  rep(i , 0 , sz(ed)-1){
    if(id[i] == 1){
      int w = ed[i].F , v =ed[i].S.F , u =ed[i].S.S ;
      int lc = lca2(v,u) ;
      G[v].pb({w,lc});
      G[u].pb({w,lc});
    }
  }
  rep(i ,1, n){
    if(mark[i] == 1)continue ;
    dfs(i) ;
  }
  for(int v : tp){
    rep(i , 1 ,lg){
      p[v][i] = p[p[v][i-1]][i-1];
      mn[v][i] = min(mn[v][i-1] , mn[p[v][i-1]][i-1]) ;
      mn2[v][i] = max(mn2[v][i-1] , mn2[p[v][i-1]][i-1]) ;
    }
  }
}

int getMinimumFuelCapacity(int v, int u) {
v++ ;u++;
  if(find(v)!=find(u))return -1 ;
  int ans = lca(v,u);
  if(ans == inf)return -1 ;
  return ans;
}
/* g++ -Wall -lm -static -DEVAL -o swap -O2 swap.cpp grader.cpp -std=c++17 */

Compilation message (stderr)

swap.cpp: In function 'void bui(int, int)':
swap.cpp:33:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for(auto [w,u] : T[v]){
      |            ^
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:43:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |   for(auto [w,u] : T[v]){
      |            ^
swap.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   for(auto [w,u] : G[v]){
      |            ^

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