Submission #1065213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065213		vjudge1	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 KiB

swap

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 17;
int n, m, q, lg, c[N], ans[N];
int r[N], d[N], p[20][N];
tuple <int, int, int> e[N];
vector <int> adj[N];
bool ex[N];
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);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    lg = __lg(n + m);
    for (int i = 1, u, v, w; i <= m; ++i)
    {
        cin >> u >> v >> w;
        ++u, ++v;
        e[i] = {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);
        }
    }
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        ++u, ++v;
        int z = lca (u, v);
        if (ex[z])
        {
            cout << ans[z] << "\n";
            continue;
        }
        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)
        {
            cout << "-1\n";
            continue;
        }
        cout << ans[z] << "\n";
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccE5LzOg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYkgRSh.o:swap.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccE5LzOg.o: in function `main':
grader.cpp:(.text.startup+0x1c3): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x217): undefined reference to `getMinimumFuelCapacity(int, int)'
collect2: error: ld returned 1 exit status