Submission #973056

#	Time	Username	Problem	Language	Result	Execution time	Memory
973056		Younis_Dwai	Swapping Cities (APIO20_swap)	C++14	100 / 100	309 ms	67412 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define in insert
#define F first
#define S second
vector<int> adj[300009];
int par1[300009],par[300009][21],depth[300009],cnt[300009],nxt=0,good[300009],val[3000009];
int get_par(int node){
    if(par1[node]==node) return node;
    return par1[node]=get_par(par1[node]);
}
void merg(int u,  int v ,int w){
     int uu=get_par(u);
     int vv=get_par(v);
     nxt++;
     val[nxt]=w;
     if(uu==vv){
        adj[nxt].pb(uu);
        cnt[u]++;
        cnt[v]++;
        good[nxt]=1;
        par1[uu]=nxt;
        return ;
     }
     adj[nxt].pb(uu);
     adj[nxt].pb(vv);
     cnt[u]++;
     cnt[v]++;
     par1[uu]=nxt;
     par1[vv]=nxt;
     if(cnt[u]>=3 || cnt[v]>=3) good[nxt]=1;
     return ;
}
void dfs(int node , int p){
     par[node][0]=p;
     for(int i=1;i<=20;i++) par[node][i]=par[par[node][i-1]][i-1];
     for(auto u : adj[node]){
         depth[u]=1+depth[node];
         dfs(u,node);
         good[node]|=good[u];
     }
     //cout<<" # "<<node<<' '<<good[node]<<' '<<val[node]<<endl;
     return ;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
     nxt=N-1;
     for(int i=0;i<N+M;i++) par1[i]=i;
     vector<pair<int,pair<int,int>>> v;
     for(int i=0;i<M;i++){
         v.pb({W[i],{U[i],V[i]}});
     }
     sort(v.begin(),v.end());
     for(auto u : v){
         merg(u.S.F,u.S.S,u.F);
     }
     dfs(nxt,nxt);
     return ;
}
int lca(int u , int v){
    if(depth[v]>depth[u]) swap(u,v);
    for(int i=20;i>=0;i--) if(depth[u]-(1<<i)>=depth[v]) u=par[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    return par[u][0];
}
int getMinimumFuelCapacity(int X, int Y) {
    int lc=lca(X,Y);
    //cout<<" @ "<<X<<' '<<Y<<' '<<lc<<endl;
    if(good[lc]==1) return val[lc];
    for(int i=20;i>=0;i--) if(good[par[lc][i]]==0) lc=par[lc][i];
    lc=par[lc][0];
    if(good[lc]) return val[lc];
    return -1;
}

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