Submission #1259051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259051		cpismylifeOwO	Swapping Cities (APIO20_swap)	C++20	100 / 100	192 ms	69968 KiB

swap

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

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
const int MaxLog = 20;

int ni, mi;
vector<int> Ui, Vi, Wi;

#ifdef cpismylifeOwO
void Inp()
{
    cin >> ni >> mi;
    for (int x = 1; x <= mi; x++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        Ui.push_back(u);
        Vi.push_back(v);
        Wi.push_back(w);
    }
}
#endif // cpismylifeOwO

struct Edge
{
    int u, v, w;

    bool operator < (const Edge& other) const
    {
        return this->w < other.w;
    }
};

int n, m;
Edge edges[MaxN];
vector<int> child[MaxN];
int parents[MaxN];
int sz[MaxN];
int root[MaxN];
bool isline[MaxN];
int st[MaxN];
int ed[MaxN];

int FindSet(int p)
{
    if (parents[p] == p)
    {
        return p;
    }
    parents[p] = FindSet(parents[p]);
    return parents[p];
}

bool UnionSet(int a, int b, int r)
{
    int pa = FindSet(a), pb = FindSet(b);
    if (pa == pb)
    {
        root[pa] = r;
        isline[pa] = false;
        return !isline[pa];
    }
    if (sz[pa] < sz[pb])
    {
        swap(pa, pb);
        swap(a, b);
    }
    isline[pa] &= isline[pb];
    if (isline[pa])
    {
        if (st[pa] == a && (st[pb] == b || ed[pb] == b))
        {
            st[pa] = st[pb] ^ ed[pb] ^ b;
        }
        else if (ed[pa] == a && (st[pb] == b || ed[pb] == b))
        {
            ed[pa] = st[pb] ^ ed[pb] ^ b;
        }
        else
        {
            isline[pa] = false;
        }
    }
    root[pa] = r;
    sz[pa] += sz[pb];
    parents[pb] = pa;
    return !isline[pa];
}

bool good[MaxN];
int BinLift[MaxLog][MaxN];
int par[MaxN];
int h[MaxN];

void PreDFS(int u)
{
    for (int x : child[u])
    {
        h[x] = h[u] + 1;
        par[x] = u;
        PreDFS(x);
    }
}

void Build()
{
    for (int x = 1; x <= n + m; x++)
    {
        BinLift[0][x] = par[x];
    }
    for (int x = 1; x < MaxLog; x++)
    {
        for (int y = 1; y <= n + m; y++)
        {
            BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]];
        }
    }
}

int LCA(int u, int v)
{
    if (h[u] != h[v])
    {
        if (h[u] > h[v])
        {
            swap(u, v);
        }
        int k = h[v] - h[u];
        for (int x = MaxLog - 1; x >= 0; x--)
        {
            if (k & (1 << x))
            {
                v = BinLift[x][v];
            }
        }
    }
    if (u == v)
    {
        return v;
    }
    for (int x = MaxLog - 1; x >= 0; x--)
    {
        if (BinLift[x][u] != BinLift[x][v])
        {
            u = BinLift[x][u];
            v = BinLift[x][v];
        }
    }
    return par[u];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
    n = N;
    m = M;
    for (int x = 0; x < m; x++)
    {
        edges[x + 1].u = U[x] + 1;
        edges[x + 1].v = V[x] + 1;
        edges[x + 1].w = W[x];
    }
    sort(edges + 1, edges + m + 1);
    for (int x = 1; x <= n; x++)
    {
        parents[x] = x;
        sz[x] = 1;
        isline[x] = true;
        st[x] = ed[x] = x;
        root[x] = x;
    }
    for (int x = 1; x <= m; x++)
    {
        int u = FindSet(edges[x].u), v = FindSet(edges[x].v);
        if (u == v)
        {
            child[x + n].push_back(root[u]);
            good[x + n] = UnionSet(edges[x].u, edges[x].v, x + n);
        }
        else
        {
            child[x + n].push_back(root[u]);
            child[x + n].push_back(root[v]);
            good[x + n] = UnionSet(edges[x].u, edges[x].v, x + n);
        }
    }
    PreDFS(n + m);
    Build();
    good[0] = true;
}

int getMinimumFuelCapacity(int X, int Y)
{
    int u = X + 1, v = Y + 1, lca = LCA(u, v);
    //cout << good[lca] << " ";
    if (good[lca])
    {
        return edges[lca - n].w;
    }
    for (int x = MaxLog - 1; x >= 0; x--)
    {
        int k = BinLift[x][lca];
        if (!good[k])
        {
            lca = k;
        }
    }
    lca = par[lca];
    if (lca == 0)
    {
        return -1;
    }
    return edges[lca - n].w;
}

#ifdef cpismylifeOwO
void Exc()
{
    init(ni, mi, Ui, Vi, Wi);
    int q;
    cin >> q;
    for (int x = 1; x <= q; x++)
    {
        int a, b;
        cin >> a >> b;
        cout << getMinimumFuelCapacity(a, b) << "\n";
    }
}

int main()
{
    freopen("SWAP.INP", "r", stdin);
    //freopen("SWAP.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}
#endif // cpismylifeOwO

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