Submission #1055255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055255		alexander707070	Swapping Cities (APIO20_swap)	C++14	100 / 100	600 ms	65272 KiB

swap

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

#define MAXN 200007
using namespace std;

const int inf=1e9+7;

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],parent[MAXN];
int lt[MAXN],rt[MAXN],in[MAXN],out[MAXN],num;
vector<int> query[MAXN];
vector<int> tree[MAXN],edges;
bool treeedge[MAXN];

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

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

    void reset(){
        for(int i=1;i<=n;i++){
            dsu[i]={{i,0}}; sz[i]=1; trip[i]=deg[i]=0;
            topv[i]=i;
        }
        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];

        if(in[topv[rooty]]<in[topv[rootx]])topv[rootx]=topv[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,bcc;

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 dfs(int x,int p){
    parent[x]=p;
    num++; in[x]=num;

    for(int i:tree[x]){
        if(i==p)continue;
        dfs(i,x);
    }

    out[x]=num;
}

bool subtree(int x,int y){
    return in[y]>=in[x] and out[y]<=out[x];
}

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;
            }
        }
    }

    bcc.reset();
    for(int i=1;i<=m;i++){
        if(bcc.root(e[i].from)==bcc.root(e[i].to))continue;

        tree[e[i].from].push_back(e[i].to);
        tree[e[i].to].push_back(e[i].from);

        bcc.mergev(e[i].from,e[i].to);
        treeedge[i]=true;
    }

    dfs(1,0);

    bcc.reset();
    for(int i=1;i<=m;i++){
        if(treeedge[i])continue;

        int x=bcc.root(e[i].from),y=bcc.root(e[i].to);
        while(!subtree(bcc.topv[x],bcc.topv[y])){
            bcc.mergev(x,bcc.root(parent[bcc.topv[x]]));
            x=bcc.root(x);

            bcc.tim--;
        }

        while(bcc.root(x)!=bcc.root(y)){
            bcc.mergev(y,bcc.root(parent[bcc.topv[y]]));
            y=bcc.root(y);

            bcc.tim--;
        }

        bcc.tim++;

        edges.push_back(e[i].cost);
    }
}

int getMinimumFuelCapacity(int X, int Y){
    X++; Y++;
    int ans=inf;

    if(rt[X]<=m){
        ans=e[max(rt[X],rt[Y])].cost;
    }

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

    if(r!=edges.size()+1)ans=min(ans,edges[r-1]);

    l=0; r=m+1;
    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);

    if(ans==inf)return -1;

    return ans;
}

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

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

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:203:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     if(r!=edges.size()+1)ans=min(ans,edges[r-1]);
      |        ~^~~~~~~~~~~~~~~~

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