Submission #1202547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202547		Warinchai	Swapping Cities (APIO20_swap)	C++20	100 / 100	288 ms	34904 KiB

swap

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

vector<pair<int,int>>adj[200005];
int cur;
int p[200005];
int in[200005];
int can[200005];
int n,m;
int pa[20][200005];
int mx[200005];
int lv[200005];

int fp(int a){
    return p[a]==a?a:p[a]=fp(p[a]);
}

void un(int a,int b,int w){
    if((fp(a))==(fp(b))){
        if(can[fp(a)])return;
        mx[fp(a)]=w;
        can[fp(a)]=1;
        return;
    }
    cur++;
    adj[cur].push_back({fp(a),w});
    adj[cur].push_back({fp(b),w});
    if(can[fp(a)]||can[fp(b)])can[cur]=1;
    in[a]++,in[b]++;
    if(in[a]>=3||in[b]>=3)can[cur]=1;
    p[fp(a)]=cur;
    p[fp(b)]=cur;
    mx[cur]=w;
}

int lca(int a,int b){
    if(lv[a]<lv[b])swap(a,b);
    for(int i=19;i>=0;i--)if(lv[pa[i][a]]>=lv[b])a=pa[i][a];
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(pa[i][a]!=pa[i][b])a=pa[i][a],b=pa[i][b];
    return pa[0][a];
}

void dfs(int u,int p){
    //cerr<<u<<" "<<mx[u]<<"\n";
    lv[u]=lv[p]+1;
    pa[0][u]=p;
    for(int i=1;i<20;i++)pa[i][u]=pa[i-1][pa[i-1][u]];
    for(auto x:adj[u]){
        dfs(x.first,u);
    }
}

void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    n=N,m=M;
    vector<pair<int,pair<int,int>>>edge;
    for(int i=0;i<M;i++){
        edge.push_back({W[i],{++U[i],++V[i]}});
    }
    sort(edge.begin(),edge.end());
    cur=N;
    for(int i=1;i<=2*N;i++)p[i]=i;
    for(auto x:edge){
        un(x.second.first,x.second.second,x.first);
    }
    dfs(cur,cur);
    /*cerr<<"can:\n";
    for(int i=1;i<=2*n-1;i++)cerr<<can[i]<<" ";
    cerr<<"\n";*/
}

int getMinimumFuelCapacity(int X, int Y) {
    X++,Y++;
    int rt=lca(X,Y);
    //cerr<<"QR:"<<X<<" "<<Y<<":"<<rt<<"\n";
    if(can[rt])return mx[rt];
    for(int i=19;i>=0;i--){
        if(!can[pa[i][rt]])rt=pa[i][rt];
    }
    if(rt==cur)return -1;
    return mx[pa[0][rt]];
}

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