Submission #408704

#	Time	Username	Problem	Language	Result	Execution time	Memory
408704		MOUF_MAHMALAT	Swapping Cities (APIO20_swap)	C++11	13 / 100	388 ms	41344 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct node
{
    ll u1,u2,w;
} a[200009];
ll n,p[300009],c[100009],ans[300009];
ll dp[300009][20],h[300009],logn;
vector<vector<ll> >v;
bool cmp(const node&xo,const node&yo)
{
    return xo.w<yo.w;
}
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y,ll z)
{
    c[x]++,c[y]++;
    bool is = (c[x]>2||c[y]>2);
    x=gp(x),y=gp(y);
    n++;
    p[x]=p[y]=p[n]=n;
    if(x==y)
    {
        is=1;
        v[n].push_back(x);
    }
    else
    {
        v[n].push_back(x);
        v[n].push_back(y);
    }
    if(is)
        ans[n]=z;
    else
        ans[n]=2e9;
}
void dfs(ll d,ll pp)
{
    dp[d][0]=pp;
    h[d]=h[pp]+1;
    ans[d]=min(ans[d],ans[pp]);
    for(auto z:v[d])
        dfs(z,d);
    if(ans[d]==2e9)
        ans[d]=-1;
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W)
{
    v.resize(N+M+9);
    for(ll i=0; i<M; i++)
    {
        a[i].u1=U[i];
        a[i].u2=V[i];
        a[i].w =W[i];
    }
    sort(a,a+M,cmp);
    n=N-1;
    for(ll i=0; i<N; i++)
        p[i]=i,ans[i]=2e9;
    for(ll i=0; i<M; i++)
        mrg(a[i].u1,a[i].u2,a[i].w);
    logn=log2(n)+1;
    ll root=gp(0);
    dfs(root,root);
    for(ll j=1; j<=logn; j++)
        for(ll i=0; i<=n; i++)
            dp[i][j]=dp[ dp[i][j-1] ][j-1];
}
int getMinimumFuelCapacity(int x, int y)
{
    ll lca;
    if(h[x]<h[y])
        swap(x,y);
    ll dif=h[x]-h[y];
    for(ll i=logn; i>=0; i--)
        if(dif&(1<<i))
            x=dp[x][i];
    for(ll i=logn; i>=0; i--)
        if(dp[x][i]!=dp[y][i])
            x=dp[x][i],y=dp[y][i];
    if(x==y)
        lca=x;
    else
        lca=dp[x][0];
    return ans[lca];
}

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