Submission #1065224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065224		HiepVu217	Swapping Cities (APIO20_swap)	C++17	100 / 100	318 ms	59132 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
const int Z = 3e5 + 17;
int n, m, q, lg, c[Z], ans[Z];
int r[Z], d[Z], p[20][Z];
tuple <int, int, int> e[Z];
vector <int> adj[Z];
bool ex[Z];
int root (int u)
{
    if (u == r[u])
    {
        return u;
    }
    return r[u] = root(r[u]);
}
void join (int x, int y, int z)
{
    x = root(x);
    y = root(y);
    ++n, r[n] = n;
    if (x == y)
    {
        ex[n] = 1, r[x] = n;
        adj[n].push_back(x);
    }
    else
    {
        ex[n] = ex[x] | ex[y] | z;
        r[x] = r[y] = n;
        adj[n].push_back(x);
        adj[n].push_back(y);
    }
}
int lca (int u, int v)
{
    if (d[u] < d[v])
    {
        swap (u, v);
    }
    for (int i = lg; i >= 0; --i)
    {
        if (d[p[i][u]] >= d[v])
        {
            u = p[i][u];
        }
    }
    if (u == v)
    {
        return u;
    }
    for (int i = lg; i >= 0; --i)
    {
        if (p[i][u] != p[i][v])
        {
            u = p[i][u], v = p[i][v];
        }
    }
    return p[0][u];
}
void dfs (int u, int pr)
{
    d[u] = d[pr] + 1, p[0][u] = pr;
    for (int i = 1; i <= lg; ++i)
    {
        p[i][u] = p[i - 1][p[i - 1][u]];
    }
    for (int v: adj[u])
    {
        if (v != pr)
        {
            dfs (v, u);
        }
    }
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
    n = N, m = M;
    lg = __lg(n + m);
    for (int i = 0; i < m; ++i)
    {
        int u = U[i], v = V[i], w = W[i];
        ++u, ++v;
        e[i + 1] = {w, u, v};
    }
    for (int i = 1; i <= n; ++i)
    {
        r[i] = i;
    }
    sort (e + 1, e + m + 1);
    for (int i = 1; i <= m; ++i)
    {
        auto [w, u, v] = e[i];
        ++c[u], ++c[v];
        int z = (c[u] > 2) | (c[v] > 2);
        join (u, v, z);
        ans[n] = w;
    }
    for (int i = n; i >= 0; --i)
    {
        if (!d[i])
        {
            dfs (i, 0);
        }
    }
}
int getMinimumFuelCapacity(int u, int v)
{
    ++u, ++v;
    int z = lca (u, v);
    if (ex[z])
    {
        return ans[z];
    }
    for (int i = lg; i >= 0; --i)
    {
        if (p[i][z] && !ex[p[i][z]])
        {
            z = p[i][z];
        }
    }
    z = p[0][z];
    if (!z)
    {
        return -1;
    }
    return ans[z];
}

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