Submission #568300

#	Time	Username	Problem	Language	Result	Execution time	Memory
568300		hibiki	Swapping Cities (APIO20_swap)	C++11	100 / 100	325 ms	55504 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second

// global
int n,m;
int deg[100005],l[300005],mn[300005],deep[300005];
int spa[300005][20];
vector<int> v[300005];
priority_queue<pair<int,pair<int,int> > > pq;

int fi(int idx)
{
    if(l[idx] == idx) return idx;
    return l[idx] = fi(l[idx]);
}

void uni(int x,int y,int w)
{
    bool chk = deg[x] > 1 | deg[y] > 1;
    deg[x]++;
    deg[y]++;
    x = fi(x), y = fi(y);
    if(x == y)
    {
        if(!mn[x])
            mn[x] = w;
        return ;
    }
    l[x] = l[y] = n;
    if(chk || mn[x] || mn[y])
        mn[n] = w;
    v[n].pb(x);
    v[n].pb(y);
    n++;
}

void dfs(int nw,int fa)
{
    for(auto go: v[nw])
    {
        if(go == fa) continue;
        if(!mn[go]) mn[go] = mn[nw];
        deep[go] = deep[nw] + 1;
        spa[go][0] = nw;
        dfs(go, nw);
    }
}

int query(int a,int b)
{
    if(deep[a] > deep[b]) swap(a,b);
    int dif = deep[b] - deep[a];
    for(int  i = 0; i < 20; i++)
        if((1<<i)&dif)
            b = spa[b][i];
    if(a == b) return mn[a];
    for(int i = 19; i >= 0; i--)
    {
        if(spa[a][i] != spa[b][i])
        {
            a = spa[a][i];
            b = spa[b][i];
        }
    }
    return mn[spa[a][0]];
}

void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W)
{
    n = N, m = M;
    memset(spa, -1, sizeof(spa));
    for(int i = 0; i < 300005; i++)
        l[i] = i;
    for(int i = 0; i < m; i++)
        pq.push({-W[i],{U[i],V[i]}});
    while(!pq.empty())
    {
        int x = pq.top().s.f, y = pq.top().s.s, w = -pq.top().f;
        pq.pop();
        uni(x,y,w);
    }
    dfs(n - 1, -1);
    for(int i = 0; i < 300005; i++)
        if(!mn[i]) mn[i] = -1;
    for(int j = 1; j < 20; j++)
    {
        for(int i = 0; i < n; i++)
        {
            if(spa[i][j - 1] == -1) continue;
            spa[i][j] = spa[spa[i][j - 1]][j - 1];
        }
    }
    return ;
}

int getMinimumFuelCapacity(int X, int Y)
{
    return query(X,Y);
}

Compilation message (stderr)

swap.cpp: In function 'void uni(int, int, int)':
swap.cpp:24:23: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   24 |     bool chk = deg[x] > 1 | deg[y] > 1;
      |                ~~~~~~~^~~

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