Submission #1094335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094335		vjudge1	Swapping Cities (APIO20_swap)	C++17	100 / 100	208 ms	80684 KiB

swap

#include <bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 1e6 + 5;
const int LG = 21;
int n,m,node,dsu[maxN],val[maxN],deg[maxN];
int up[LG][maxN],lg[maxN],res[maxN],dep[maxN];
bool swp[maxN];
vector<int> adj[maxN];
struct Tedge
{
    int x,y,w;
}
e[maxN];
int findset(int u)
{
    return dsu[u] == u ? u : dsu[u] = findset(dsu[u]);
}
void add(int u,int v,int w)
{
    int v1 = v,u1 = u;
    deg[u]++;deg[v]++;
    ++node;
    u = findset(u);v = findset(v);
    dsu[u] = dsu[v] = node;
    dsu[node] = node;
    val[node] = w;
    adj[node].push_back(u);
    if (u != v) adj[node].push_back(v);
    if (u == v || swp[u] || swp[v] || deg[u1] > 2 || deg[v1] > 2) swp[node] = true;
    else swp[node] = false;
}
bool cmp(const Tedge& a,const Tedge& b)
{
    return a.w < b.w;
}
void dfs(int u,int par)
{
    if (swp[u]) res[u] = val[u];
    else res[u] = res[par];
    up[0][u] = par;
    for (int v : adj[u])
    {
        dep[v] = dep[u] + 1;
        dfs(v,u);
    }
}
void presolve()
{
    lg[1] = 0;
    for (int i = 2;i <= node;++i) lg[i] = lg[i / 2] + 1;
    for (int j = 1;j < LG;++j)
        for (int i = 1;i <= node;++i)
        up[j][i] = up[j - 1][up[j - 1][i]];
}
int lca(int u,int v)
{
    int u1 = u,v1 = v;
    if (dep[u] < dep[v]) swap(u,v);
    int k = dep[u] - dep[v];
    for (int i = lg[k];i >= 0;--i)
        if (k & (1 << i)) u = up[i][u];
    if (u == v) return u;
    k = dep[u];
    for (int i = lg[k];i >= 0;--i)
    {
        if (up[i][u] != up[i][v])
        {
            u = up[i][u];
            v = up[i][v];
        }
    }
    return up[0][u];
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W)
{
    n = N;m = M;
    node = n;
    for (int i = 1;i <= M;++i)
    {
        e[i].x = U[i - 1] + 1;
        e[i].y = V[i - 1] + 1;
        e[i].w = W[i - 1];
    }
    sort(e + 1,e + m + 1,cmp);
    for (int i = 1;i <= n;++i)
    {
        dsu[i] = i;
        if (deg[i] >= 3) swp[i] = true;
        else swp[i] = false;
    }
    for (int i = 1;i <= m;++i)
    {
        //cout << e[i].x << " " << e[i].y << " " << e[i].w << "\n";
        add(e[i].x,e[i].y,e[i].w);
    }
    //cout << "A\n";
    //for (int i = 1;i <= node;++i) for (int v : adj[i]) cout << i << " " << v << "\n";
    res[0] = -1;dep[node] = 0;
    dfs(node,0);
    presolve();
}
int getMinimumFuelCapacity(int X, int Y)
{
    ++X,++Y;
    //cout << X << " " << Y << " " << swp[lca(X,Y)] << " ";
    return res[lca(X,Y)];
}

Compilation message (stderr)

swap.cpp: In function 'int lca(int, int)':
swap.cpp:58:9: warning: unused variable 'u1' [-Wunused-variable]
   58 |     int u1 = u,v1 = v;
      |         ^~
swap.cpp:58:16: warning: unused variable 'v1' [-Wunused-variable]
   58 |     int u1 = u,v1 = v;
      |                ^~

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