Submission #1173047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173047		AlgorithmWarrior	Swapping Cities (APIO20_swap)	C++20	100 / 100	165 ms	36700 KiB

swap

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

using namespace std;

int const LOG=20;
int const MAX=2e5+5;
struct edge{
    int u,v,w;
    bool operator<(edge ot){
        return w<ot.w;
    }
}edges[MAX];
int val[MAX];
pair<int,int>lant[MAX];
int lift[MAX][LOG];
vector<int>sons[MAX];
int h[MAX];

bool find_link(multiset<int>&ms,int u,int v){
    if(ms.find(u)==ms.end() || ms.find(v)==ms.end())
        return 0;
    ms.erase(ms.find(u));
    ms.erase(ms.find(v));
    return 1;
}

struct DSU{
    int total;
    int tata[MAX];
    void initializare(int n){
        total=n;
        int i;
        for(i=0;i<total;++i){
            tata[i]=i;
            lant[i]={i,i};
        }
    }
    int root(int nod){
        if(tata[nod]==nod)
            return nod;
        return tata[nod]=root(tata[nod]);
    }
    void uneste(int u,int v,int w){
        int ru=root(u);
        int rv=root(v);
        if(ru==rv){
            if(!val[ru]){
                val[ru]=w;
                lant[ru]={-1,-1};
            }
        }
        else{
            tata[ru]=total;
            tata[rv]=total;
            tata[total]=total;
            lift[ru][0]=total;
            lift[rv][0]=total;
            sons[total]={ru,rv};
            if(lant[ru].first!=-1 && lant[rv].first!=-1){
                multiset<int>ms;
                ms.insert(lant[ru].first);
                ms.insert(lant[ru].second);
                ms.insert(lant[rv].first);
                ms.insert(lant[rv].second);
                if(find_link(ms,u,v))
                    lant[total]={*ms.begin(),*next(ms.begin())};
                else{
                    lant[total]={-1,-1};
                    val[total]=w;
                }
            }
            else{
                lant[total]={-1,-1};
                val[total]=w;
            }
            ++total;
        }
    }
}dsu;

void dfs(int nod){
    for(auto fiu : sons[nod]){
        h[fiu]=h[nod]+1;
        dfs(fiu);
    }
}

void init(int N,int M,vector<int>U,vector<int>V,vector<int>W){
    int i;
    for(i=0;i<M;++i)
        edges[i]={U[i],V[i],W[i]};
    sort(edges,edges+M);
    dsu.initializare(N);
    for(i=0;i<M;++i)
        dsu.uneste(edges[i].u,edges[i].v,edges[i].w);
    dfs(dsu.total-1);
    lift[dsu.total-1][0]=dsu.total-1;
    int j;
    for(j=1;j<LOG;++j)
        for(i=0;i<dsu.total;++i)
            lift[i][j]=lift[lift[i][j-1]][j-1];
    if(!val[dsu.total-1]){
        for(i=0;i<dsu.total;++i)
            val[i]=-1;
    }
    else{
        for(i=dsu.total-2;i>=0;--i)
            if(!val[i])
                val[i]=val[lift[i][0]];
    }
}

int lca(int u,int v){
    if(h[u]<h[v])
        swap(u,v);
    int dif=h[u]-h[v];
    int i;
    for(i=0;i<LOG;++i)
        if(dif&(1<<i))
            u=lift[u][i];
    if(u==v)
        return u;
    for(i=LOG-1;i>=0;--i)
        if(lift[u][i]!=lift[v][i]){
            u=lift[u][i];
            v=lift[v][i];
        }
    return lift[u][0];
}

int getMinimumFuelCapacity(int X, int Y) {
    return val[lca(X,Y)];
}

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