Submission #882721

#	Time	Username	Problem	Language	Result	Execution time	Memory
882721		12345678	Swapping Cities (APIO20_swap)	C++17	100 / 100	257 ms	62912 KiB

swap

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

using namespace std;

const int nx=3e5+5, kx=19;
int lvl[nx], pa[nx][kx], dsu[nx], cnt, vl[nx], c[nx], f, l[nx];
vector<tuple<int, int, int>> v;
vector<int> d[nx];

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

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1; pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:d[u])
    {
        if (!c[v]) vl[v]=vl[u];
        dfs(v, u);
    }
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    cnt=N;
    for (int i=0; i<nx; i++) dsu[i]=i;
    for (int i=0; i<M; i++) v.push_back({W[i], U[i], V[i]});
    sort(v.begin(), v.end());
    for (auto [z, x, y]:v)
    {
        vl[cnt]=z;
        l[x]++; l[y]++;
        if (find(x)==find(y)) d[cnt].push_back(find(x)), dsu[find(x)]=cnt, c[cnt++]=1;
        else
        {
            int px=find(x), py=find(y);
            dsu[px]=cnt; dsu[py]=cnt;
            d[cnt].push_back(px);
            d[cnt].push_back(py);
            //cout<<px<<' '<<py<<' '<<d[px].size()<<' '<<d[py].size()<<'\n';
            c[cnt++]=c[px]||c[py]||l[x]>=3||l[y]>=3;
        }
    }
    if (!c[cnt-1]) f=1;
    else dfs(cnt-1, cnt-1);
}

int getMinimumFuelCapacity(int X, int Y) {
    if (f) return -1;
    else return vl[lca(X, Y)];
}

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