Submission #394291

#	Time	Username	Problem	Language	Result	Execution time	Memory
394291		thuanqvbn03	Swapping Cities (APIO20_swap)	C++17	100 / 100	239 ms	17056 KiB

swap

//Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200005;

struct Comp
{
    int endPoint[2], parent, size, val;
} comp[MAX_N];

int wParent[MAX_N], depth[MAX_N];
vector<int> adj[MAX_N];

int findParent(int node)
{
    while (comp[node].parent != -1)
    {
        node = comp[node].parent;
    }
    return node;
}

void join(int u, int v, int w)
{
    int x = findParent(u), y = findParent(v);
    if (x == y)
    {
        if (comp[x].val < 0)
        {
            comp[x].val = w;
        }
        return;
    }
    if (comp[x].size < comp[y].size)
    {
        swap(x, y);
        swap(u, v);
    }
    comp[x].size += comp[y].size;
    comp[y].parent = x;
    wParent[y] = w;
    adj[x].push_back(y);
    if (comp[x].val < 0 && comp[y].val < 0 && (u == comp[x].endPoint[0] || u == comp[x].endPoint[1]) && (v == comp[y].endPoint[0] || v == comp[y].endPoint[1]))
    {
        if (u == comp[x].endPoint[0])
        {
            comp[x].endPoint[0] = comp[x].endPoint[1];
        }
        comp[x].endPoint[1] = (v == comp[y].endPoint[0] ? comp[y].endPoint[1] : comp[y].endPoint[0]);
    }
    else if (comp[x].val < 0)
    {
        comp[x].val = w;
    }
}

void dfs(int node)
{
    for (auto &u : adj[node])
    {
        depth[u] = depth[node] + 1;
        dfs(u);
    }
}

void init(int numNode, int numEdge, vector<int> u, vector<int> v, vector<int> w)
{
    vector<int> index(numEdge);
    iota(index.begin(), index.end(), 0);
    sort(index.begin(), index.end(), [&](int x, int y) { return w[x] < w[y]; });
    for (int i = 0; i < numNode; i++)
    {
        comp[i].endPoint[0] = comp[i].endPoint[1] = i;
        comp[i].parent = comp[i].val = -1;
        comp[i].size = 1;
    }
    for (auto &id : index)
    {
        join(u[id], v[id], w[id]);
    }
    for (int node = 0; node < numNode; node++)
    {
        if (comp[node].parent < 0)
        {
            dfs(node);
        }
    }
}

int getMinimumFuelCapacity(int u, int v)
{
    if (findParent(u) != findParent(v))
    {
        return -1;
    }
    int resuft = -1;
    while (u != v)
    {
        if (depth[u] < depth[v])
        {
            swap(u, v);
        }
        resuft = max(resuft, wParent[u]);
        u = comp[u].parent;
    }
    while (u >= 0 && comp[u].val < 0)
    {
        resuft = max(resuft, wParent[u]);
        u = comp[u].parent;
    }
    return (u < 0 ? -1 : max(resuft, comp[u].val));
}

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