Submission #977937

#	Time	Username	Problem	Language	Result	Execution time	Memory
977937		Tuanlinh123	Swapping Cities (APIO20_swap)	C++17	100 / 100	230 ms	211168 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=1000005, inf=1e9;
vector <pll> euler;
pll sp[20][maxn*2];
vector <ll> A[maxn];
ll notline[maxn], c[maxn], lca[maxn], ne[maxn]; 

namespace DSU
{
    ll cr, dsu[maxn], l[maxn], r[maxn];
    ll Find(ll i){return dsu[i]>=0?dsu[i]=Find(dsu[i]):i;}
    void init(ll sz)
    {
        cr=sz-1, memset(dsu, -1, sizeof(dsu));
        for (ll i=0; i<sz; i++) l[i]=r[i]=i;
    }

    void Union(ll a, ll b, ll w)
    {
        ll Pa=Find(a), Pb=Find(b);
        if (Pa==Pb)
        {
            A[++cr].pb(Pa), notline[cr]=1, c[cr]=w;
            dsu[Pa]=cr, l[cr]=r[cr]=-1;
            return;
        }
        A[++cr].pb(Pa), A[cr].pb(Pb), c[cr]=w;
        dsu[Pa]=dsu[Pb]=cr;
        if (a!=l[Pa]) swap(l[Pa], r[Pa]);
        if (b!=l[Pb]) swap(l[Pb], r[Pb]);
        if (a!=l[Pa] || b!=l[Pb])
            notline[cr]=1, l[cr]=r[cr]=-1;
        else l[cr]=r[Pa], r[cr]=r[Pb];
    }
}

void dfs(ll u)
{
    if (notline[u]) ne[u]=u;
    lca[u]=sz(euler)+1;
    euler.pb({lca[u], u});
    for (ll v:A[u])
    {
        ne[v]=ne[u], dfs(v);
        euler.pb({lca[u], u});
    }
}

void init_sp()
{
    ll n=sz(euler);
    for (ll i=0; i<n; i++)
        sp[0][i]=euler[i];
    for (ll i=1; i<20; i++)
        for (ll j=0; j+(1<<i)<=n; j++)
            sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
}

ll LCA(ll u, ll v)
{
    ll l=lca[u], r=lca[v];
    if (l>r) swap(l, r);
    ll j=__lg(r-l+1);
    return min(sp[j][l], sp[j][r-(1<<j)+1]).se;
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) 
{
    DSU::init(n);
    vector <pair<ll, pll>> edge;
    for (ll i=0; i<m; i++)
        edge.pb({W[i], {U[i], V[i]}});
    sort(edge.begin(), edge.end());
    for (auto [w, e]:edge) DSU::Union(e.fi, e.se, w);
    ne[DSU::cr]=-1, dfs(DSU::cr), init_sp();
}

int getMinimumFuelCapacity(int X, int Y) 
{
    ll p=LCA(X, Y);
    if (ne[p]==-1) return -1;
    return c[ne[p]];
}

Compilation message (stderr)

swap.cpp: In function 'void init_sp()':
swap.cpp:67:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |             sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<i-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