Submission #394289

#	Time	Username	Problem	Language	Result	Execution time	Memory
394289		thuanqvbn03	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 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));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef Flower_On_Stone
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
    int numNode, numEdge;
    cin >> numNode >> numEdge;
    vector<int> u(numEdge), v(numEdge), w(numEdge);
    for (int i = 0; i < numEdge; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
    }
    init(numNode, numEdge, u, v, w);
    int numQuery;
    cin >> numQuery;
    while (numQuery--)
    {
        int u, v;
        cin >> u >> v;
        cout << getMinimumFuelCapacity(u, v) << '\n';
    }
    return 0;
}

Compilation message (stderr)

/tmp/ccUQZXJT.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccYXdUoF.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status