Submission #1096043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096043		onlk97	Swapping Cities (APIO20_swap)	C++14	100 / 100	215 ms	67308 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;
}
int dsu0[100010],dsu[300010],Deg[100010],deg[300010][4],hvcyc[300010];
int prt0(int n){
    if (dsu0[n]==n) return n;
    return dsu0[n]=prt0(dsu0[n]);
}
void unn0(int u,int v){
    dsu0[prt0(u)]=dsu0[prt0(v)];
}
int prt(int n){
    if (dsu[n]==n) return n;
    return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
    u=prt(u); v=prt(v);
    if (u==v) return;
    dsu[u]=v;
    hvcyc[v]|=hvcyc[u];
    for (int i=0; i<4; i++) deg[v][i]+=deg[u][i];
}
vector <int> krt[300010];
int cost[300010],ans[300010];
int dep[300010],fa[20][300010];
void dfs(int cur,int prv,int heeh){
    if (prv) dep[cur]=dep[prv]+1;
    fa[0][cur]=prv;
    if (hvcyc[cur]||deg[cur][3]) heeh=min(heeh,cost[cur]);
    ans[cur]=heeh;
    for (int i:krt[cur]) dfs(i,cur,heeh);
}
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+1];
    for (int i=1; i<=M; i++) edg[i]={{U[i-1]+1,V[i-1]+1},W[i-1]};
    sort(edg+1,edg+M+1,cmp);
    for (int i=1; i<=N; i++) dsu0[i]=i;
    for (int i=1; i<=N; i++) deg[i][0]=1;
    for (int i=1; i<=N+M; i++) dsu[i]=i;
    for (int i=1; i<=M; i++){
        if (prt0(edg[i].first.first)==prt0(edg[i].first.second)){
            int u=prt(edg[i].first.first);
            krt[N+i].push_back(u);
            unn(u,N+i);
            hvcyc[N+i]=1;
        } else {
            int u=prt(edg[i].first.first),v=prt(edg[i].first.second);
            krt[N+i].push_back(u); krt[N+i].push_back(v);
            unn(u,N+i); unn(v,N+i);
            unn0(edg[i].first.first,edg[i].first.second);
            if (Deg[edg[i].first.first]<3) deg[N+i][Deg[edg[i].first.first]]--;
            if (Deg[edg[i].first.second]<3) deg[N+i][Deg[edg[i].first.second]]--;
            Deg[edg[i].first.first]++; Deg[edg[i].first.second]++;
            deg[N+i][min(3,Deg[edg[i].first.first])]++;
            deg[N+i][min(3,Deg[edg[i].first.second])]++;
        }
        cost[N+i]=edg[i].second;
    }
    dfs(N+M,0,2e9);
    for (int i=1; i<20; i++){
        for (int j=1; j<=N+M; 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 op=ans[l];
    if (op>1e9) op=-1;
    return op;
}

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