Submission #1054619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054619		alexander707070	Swapping Cities (APIO20_swap)	C++14	0 / 100	2037 ms	44204 KiB

swap

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

#define MAXN 100007
using namespace std;

const int inf=1e9+7;

int n,m,a[MAXN],b[MAXN],c[MAXN],dep[MAXN];
vector<int> tree[MAXN],v[MAXN];
int parent[MAXN],res[MAXN];

struct edge{
    int from,to,cost;

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

struct unionfind{
    int dsu[MAXN];

    void init(){
        for(int i=1;i<=n;i++)dsu[i]=i;
    }

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

    void mergev(int x,int y){
        if(root(x)==root(y))return;

        dsu[root(x)]=root(y);
    }

    bool connected(int x,int y){
        return root(x)==root(y);
    }
}graph;

void dfs(int x,int p){
    parent[x]=p;
    dep[x]=dep[p]+1;

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

pair<int,int> dp[MAXN][20];
bool li[MAXN][20];

pair<int,int> ff(int x,int p){
    if(p==0)return {parent[x],min(res[x],res[parent[x]])};
    if(x==0)return {0,inf};

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p].first=ff(ff(x,p-1).first,p-1).first;
    dp[x][p].second=min( ff(x,p-1).second , ff(ff(x,p-1).first,p-1).second );

    return dp[x][p];
}

int getbranch(int x,int y){
    int ans=inf;

    if(dep[x]<dep[y])swap(x,y);

    if(x==y or parent[x]==y)return inf;

    if(dep[x]!=dep[y]){
        x=parent[x];

        for(int i=19;i>=0;i--){
            if(dep[x]-dep[y]>(1<<i)){
                ans=min(ans,ff(x,i).second);
                x=ff(x,i).first;
            }
        }
        
        if(parent[x]==y)return ans;

        if(dep[x]>dep[y]){
            x=parent[x];
            ans=min(ans,res[x]);
        }
    }

    x=parent[x];
    y=parent[y];

    ans=min(ans,res[x]);

    for(int i=19;i>=0;i--){
        if(ff(x,i).first!=0 and ff(y,i).first!=0 and ff(x,i).first!=ff(y,i).first){
            ans=min(ans,ff(x,i).second);
            ans=min(ans,ff(y,i).second);

            x=ff(x,i).first; y=ff(y,i).first;
        }
    }

    if(x!=y)ans=min(ans,res[parent[x]]);

    return ans;
}

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++){
        a[i]=U[i-1]+1; b[i]=V[i-1]+1; c[i]=W[i-1];

        v[a[i]].push_back(c[i]);
        v[b[i]].push_back(c[i]);

        e[i]={a[i],b[i],c[i]};
    }

    for(int i=1;i<=n;i++){
        sort(v[i].begin(),v[i].end());

        res[i]=inf;
        if(v[i].size()>=3)res[i]=v[i][2];
    }
    res[0]=inf;

    sort(e+1,e+m+1);
    graph.init();

    for(int i=1;i<=m;i++){
        if(graph.connected(e[i].from,e[i].to))continue;
        
        tree[e[i].from].push_back(e[i].to);
        tree[e[i].to].push_back(e[i].from);

        graph.mergev(e[i].from,e[i].to);
    }

    dfs(1,0);
}

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

    if(ans==inf)return -1;
    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: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27