Submission #1105678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105678		ASN49K	Swapping Cities (APIO20_swap)	C++14	100 / 100	173 ms	31048 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()


const int N=100'000,LG=16;
int cost[2*N],t[2*N],tt[2*N][LG+1],cnt_edges[N],size,tin[2*N],tout[2*N],l_child[2*N],r_child[2*N];
int root(int x)
{
    if(t[x]!=x)
    {
        t[x]=root(t[x]);
    }
    return t[x];
}
void unite(int x,int y,int c)
{
    bool ok=(++cnt_edges[x]>=3 || ++cnt_edges[y]>=3);
    x=root(x);
    y=root(y);
    if(x!=y)
    {
        tt[x][0]=t[x]=size;
        l_child[size]=x;
        tt[y][0]=t[y]=size;
        r_child[size]=y;
        if(ok || cost[x]>0 || cost[y]>0)
        {
            cost[size]=c;
        }
        tt[size][0]=t[size]=size;
        size++;
    }
    else if(!cost[x])
    {
        cost[x]=c;
    }
}

void dfs(int nod,int n)
{
    static int timp=0;
    tin[nod]=++timp;
    if(nod>=n)
    {
        dfs(l_child[nod],n);
        dfs(r_child[nod],n);
    }
    tout[nod]=timp;
}

void init(int n, int m,std::vector<int> x, std::vector<int> y, std::vector<int> w)
{
    vector<int>ord(m);
    iota(all(ord) , 0);
    sort(all(ord) , [&](int x,int y){
        return w[x]<w[y];
    });
    for(int i=0;i<n;i++)
    {
        tt[i][0]=t[i]=i;
    }
    size=n;
    for(int i=0;i<m;i++)
    {
        unite(x[ord[i]] , y[ord[i]] , w[ord[i]]);
    }

    for(int i=1;i<=LG;i++)
    {
        for(int j=0;j<size;j++)
        {
            tt[j][i]=tt[tt[j][i-1]][i-1];
        }
    }
    for(int i=size-1;i>=0;i--)
    {
        if(!tin[i])
        {
            dfs(i,n);
        }
    }
}

bool is_parent(int x,int y)
{
    return tin[x]<=tin[y] && tout[y]<=tout[x];
}
int lca(int x,int y)
{
    if(is_parent(x,y))
    {
        return x;
    }
    if(is_parent(y,x))
    {
        return y;
    }
    for(int i=LG;i>=0;i--)
    {
        if(!is_parent(tt[x][i],y))
        {
            x=tt[x][i];
        }
    }
    return tt[x][0];
}
int getMinimumFuelCapacity(int x, int y)
{
    if(root(x)!=root(y) || cost[root(x)]==0)
    {
        return -1;
    }
    int l=lca(x,y);
    if(cost[l]>0)
    {
        return cost[l];
    }

    for(int i=LG;i>=0;i--)
    {
        if(cost[tt[l][i]]==0)
        {
            l=tt[l][i];
        }
    }
    return cost[tt[l][0]];
}

/*
5 6
0 1 4
*/

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