Submission #729584

#	Time	Username	Problem	Language	Result	Execution time	Memory
729584		onepunchac168	Swapping Cities (APIO20_swap)	C++14	13 / 100	224 ms	47308 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mask(x) (1LL<<(x))
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
ll n,m;
ll parent[100005][20];
ll mx[100005][20];
vector <ii> vt[100005];
ll sz[100005];
ll solve(ll aa,ll bb)
{
    if (aa==-1&&bb==-1)
    {
        return -1;
    }
    if (aa==-1)
    {
        return bb;
    }
    if (bb==-1)
    {
        return aa;
    }
    return min(aa,bb);
}
ll solvea(ll aa,ll bb)
{
    if (aa==-1&&bb==-1)
    {
        return -1;
    }
    if (aa==-1)
    {
        return bb;
    }
    if (bb==-1)
    {
        return aa;
    }
    return max(aa,bb);
}
struct DSU{
    ll lab[100005];
    bool check[100005];
    ll tmp[100005];
    ll countedge[100005];
    void makeset(int u)
    {
        lab[u]=-1;
        tmp[u]=-1;
        countedge[u]=0;
    }
    ll findset(int u)
    {
        if (lab[u]<0)
        {
            return u;
        }
        return lab[u]=findset(lab[u]);
    }
    void Union(int u,int v,ll w)
    {
        int r=findset(u);
        int s=findset(v);
        countedge[u]++;
        countedge[v]++;
        if (r==s)
        {
            if (tmp[r]==-1)
            {
                tmp[r]=w;
            }
            return;
        }
        if (lab[r]>lab[s])
        {
            swap(r,s);
        }
        lab[r]+=lab[s];
        lab[s]=r;
        if (tmp[s]!=-1&&tmp[r]==-1)
        {
            tmp[r]=w;
        }
        if (countedge[u]>=3||countedge[v]>=3)
        {
            if (tmp[r]==-1)
            {
                tmp[r]=w;
            }
        }
        vt[r].pb({s,w});
    }
} dsu;
void dfs(int u)
{
    for (auto v:vt[u])
    {
        parent[v.fi][0]=u;
        mx[v.fi][0]=v.se;
        for (int i=1;i<=18;i++)
        {
            mx[v.fi][i]=max(mx[v.fi][i-1],mx[parent[v.fi][i-1]][i-1]);
            parent[v.fi][i]=parent[parent[v.fi][i-1]][i-1];
        }
        sz[v.fi]=sz[u]+1;
        if (dsu.tmp[v.fi]!=-1)
        {
            dsu.tmp[v.fi]=solvea(dsu.tmp[v.fi],v.se);
        }
        dsu.tmp[v.fi]=solvea(dsu.tmp[v.fi],dsu.tmp[u]);
        dfs(v.fi);
    }
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N-1;
    m=M-1;
    vector <iii> vta;
    for (int i=0;i<=n;i++)
    {
        dsu.makeset(i);
    }
    for (int i=0;i<=m;i++)
    {
        ll u=U[i];
        ll v=V[i];
        ll w=W[i];
        vta.pb({w,{u,v}});
    }
    sort (vta.begin(),vta.end());
    for (auto v:vta)
    {
        dsu.Union(v.se.fi,v.se.se,v.fi);
    }
    ll ss=dsu.findset(0);
    sz[ss]=0;
    dfs(ss);
}
ii lca(int u,int v)
{
    if (sz[u]>sz[v]){swap(u,v);}
    ll pp=0;
    for (int i=18;i>=0;i--)
    {
        if (sz[v]-mask(i)>=sz[u])
        {
            pp=max(pp,mx[v][i]);
            v=parent[v][i];
        }
    }
    if (u==v){return {u,pp};}
    for (int i=18;i>=0;i--)
    {
        if (parent[u][i]!=parent[v][i])
        {
            pp=max({pp,mx[u][i],mx[v][i]});
            u=parent[u][i];
            v=parent[v][i];
        }
    }
    if (u!=v)
    {
        pp=max({pp,mx[u][0],mx[v][0]});
        u=parent[u][0];
        v=parent[v][0];
    }
    return {u,pp};
}
int getMinimumFuelCapacity(int X, int Y) {
    ii aa=lca(X,Y);
    if (dsu.tmp[X]==-1)
    {
        return -1;
    }
    if (dsu.tmp[Y]==-1)
    {
        return -1;
    }
    return max(aa.se,min(dsu.tmp[X],dsu.tmp[Y]));
}

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