Submission #1055209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055209		alexander707070	Swapping Cities (APIO20_swap)	C++17	30 / 100	299 ms	32308 KiB

swap

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

#define MAXN 100007
using namespace std;

int n,m;

struct edge{
    int from,to,cost;
    
    inline friend bool operator < (edge fr,edge sc){
        return fr.cost<sc.cost;
    }
}e[MAXN];

int closest[MAXN],special[MAXN];
int lt[MAXN],rt[MAXN];
vector<int> query[MAXN];

struct union_find{
    vector< pair<int,int> > dsu[MAXN];

    int sz[MAXN],trip[MAXN],deg[MAXN],tim;

    void reset(){
        for(int i=1;i<=n;i++){
            dsu[i]={{i,0}}; sz[i]=1; trip[i]=deg[i]=0;
        }
        tim=0;
    }

    int root(int x){
        if(dsu[x].back().first==x)return dsu[x].back().first;
        return root(dsu[x].back().first);
    }

    void mergev(int x,int y){
        tim++;

        int rootx=root(x);
        int rooty=root(y);

        deg[x]++; deg[y]++;

        if(deg[x]>=3)trip[rootx]=x;
        if(deg[y]>=3)trip[rootx]=y;

        if(rootx==rooty)return;
        if(sz[rootx]<sz[rooty])swap(rootx,rooty);

        dsu[rooty].push_back({rootx,tim});
        sz[rootx]+=sz[rooty];
        if(trip[rooty]!=0)trip[rootx]=trip[rooty];
    }

    int comp(int x,int when){
        int l=0,r=dsu[x].size(),tt;

        while(l+1<r){
            tt=(l+r)/2;
            if(dsu[x][tt].second<=when){
                l=tt;
            }else{
                r=tt;
            }
        }

        return dsu[x][l].first;
    }

    int pastroot(int x,int when){
        int curr=comp(x,when);

        if(curr==x)return x;
        return pastroot(curr,when);
    }
}graph;

void build_mst(){
    graph.reset();

    for(int i=1;i<=m;i++){
        graph.mergev(e[i].from,e[i].to);

        for(int f:query[i]){
            closest[f]=graph.trip[graph.root(f)];
        }
    }
}

void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    
    n=N; m=M;
    for(int i=1;i<=m;i++){
        e[i]={U[i-1]+1,V[i-1]+1,W[i-1]};
    }

    sort(e+1,e+m+1);

    for(int i=1;i<=n;i++){
        lt[i]=0; rt[i]=m+1;
    }

    for(int i=1;i<=18;i++){
        for(int f=1;f<=m;f++)query[f].clear();

        for(int f=1;f<=n;f++){
            query[(lt[f]+rt[f])/2].push_back(f);
        }

        build_mst();

        for(int f=1;f<=n;f++){
            if(closest[f]!=0){
                rt[f]=(lt[f]+rt[f])/2;
                special[f]=closest[f];
            }else{
                lt[f]=(lt[f]+rt[f])/2;
            }
        }
    }
}

int getMinimumFuelCapacity(int X, int Y){
    X++; Y++;
    if(rt[X]==m+1)return -1;

    int ans=e[max(rt[X],rt[Y])].cost;

    int l=0,r=m+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(graph.pastroot(X,tt)==graph.pastroot(Y,tt)){
            r=tt;
        }else{
            l=tt;
        }
    }

    ans=max(ans,e[r].cost);

    return ans;
}

/*
int main(){
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});

    cout<<getMinimumFuelCapacity(1, 2)<<"\n";
    cout<<getMinimumFuelCapacity(2,4)<<"\n";
    cout<<getMinimumFuelCapacity(0,1)<<"\n";
}
*/

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