Submission #1095950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095950		onlk97	Swapping Cities (APIO20_swap)	C++14	6 / 100	167 ms	39444 KiB

swap

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

bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){
    return a.second<b.second;
}
struct dsu{
    vector <int> pa;
    void init(int n){
        pa.clear();
        for (int i=0; i<=n; i++) pa.push_back(i);
    }
    int prt(int n){
        if (pa[n]==n) return n;
        return pa[n]=prt(pa[n]);
    }
    void unn(int u,int v){
        pa[prt(u)]=pa[prt(v)];
    }
};
int weight[200010],lb[200010],dep[200010];
vector <int> krt[200010];
void dfs1(int cur,int prv){
    if (prv!=-1) dep[cur]=dep[prv]+1;
    for (int i:krt[cur]) dfs1(i,cur);
    if (lb[cur]) weight[cur]=max(lb[cur],min(weight[krt[cur][0]],weight[krt[cur][1]]));
}
void dfs2(int cur,int mn){
    weight[cur]=min(weight[cur],mn);
    for (int i:krt[cur]) dfs2(i,min(mn,weight[cur]));
}
int fa[20][2000010];
int lca(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);
    int d=dep[u]-dep[v];
    for (int i=0; i<20; i++){
        if (d&(1<<i)) u=fa[i][u];
    }
    if (u==v) return u;
    for (int i=19; i>=0; i--){
        if (fa[i][u]!=fa[i][v]){
            u=fa[i][u];
            v=fa[i][v];
        }
    }
    return fa[0][u];
}
void init(int N,int M,vector <int> U,vector <int> V,vector <int> W){
    pair <pair <int,int>,int> edg[M];
    for (int i=0; i<M; i++) edg[i]={{U[i]+1,V[i]+1},W[i]};
    sort(edg,edg+M,cmp);
    dsu d;
    d.init(2*N);
    int cnt=N;
    for (int i=0; i<=2*N; i++) weight[i]=2e9;
    for (int i=0; i<M; i++){
        int u=d.prt(edg[i].first.first),v=d.prt(edg[i].first.second);
        if (u==v){
            weight[edg[i].first.first]=min(weight[edg[i].first.first],edg[i].second);
            weight[edg[i].first.second]=min(weight[edg[i].first.second],edg[i].second);
            continue;
        }
        cnt++;
        d.unn(u,cnt);
        d.unn(v,cnt);
        krt[cnt].push_back(u); krt[cnt].push_back(v);
        fa[0][u]=cnt; fa[0][v]=cnt;
        lb[cnt]=edg[i].second;
    }
    dfs1(cnt,-1);
    dfs2(cnt,2e9);
    for (int i=1; i<20; i++){
        for (int j=1; j<=cnt; j++) fa[i][j]=fa[i-1][fa[i-1][j]];
    }
}

int getMinimumFuelCapacity(int X,int Y){
    X++; Y++;
    int l=lca(X,Y);
    int ans=weight[l];
    if (ans>1e9) ans=-1;
    return ans;
}

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