Submission #1219253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219253		vanea	Swapping Cities (APIO20_swap)	C++20	100 / 100	226 ms	81408 KiB

swap

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

const int mxN = 3e5+10;

int p[mxN], deg[mxN], pos[mxN];
int mx[mxN][22], anc[mxN][22];
int w[mxN], dep[mxN];
vector<int> adj[mxN];

int get(int x) {
    return p[x] == x ? x : p[x] = get(p[x]);
}

void uni(int a, int b, int k, bool can) {
    if(pos[a] || pos[b]) can = true;
    p[a] = p[b] = p[k] = k;
    pos[k] = can;
    adj[k].push_back(a); if(a != b) adj[k].push_back(b);
}

void dfs(int node, int p) {
    anc[node][0] = p;
    for(int j = 1; j <= 20; j++) {
        anc[node][j] = anc[anc[node][j-1]][j-1];
    }
    mx[node][0] = (pos[p] ? w[p] : 0);
    for(int j = 1; j <= 20; j++) {
        if(mx[node][j-1] != 0) mx[node][j] = mx[node][j-1];
        else mx[node][j] = mx[anc[node][j-1]][j-1];
    }
    for(auto it : adj[node]) {
        dep[it] = dep[node]+1;
        dfs(it, node);
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    iota(p, p+N+M+1, 0); int n = N;
    int cnt = n;
    vector<int> ord(M); iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return W[a] < W[b];
    });
    for(int i = 0; i < M; i++) {
        int u = U[ord[i]], v = V[ord[i]];
        w[cnt] = W[ord[i]];
        ++deg[u]; ++deg[v];
        bool can = false;
        if(deg[u] >= 3 || deg[v] >= 3) can = true;
        u = get(u); v = get(v);
        if(u == v) can = true;
        uni(u, v, cnt, can); ++cnt;
    }
    --cnt;
    dfs(cnt, cnt);
}

void jmp(int &a, int k) {
    for(int j = 20; j >= 0; j--) {
        if(k & (1 << j)) a = anc[a][j];
    }
}

int LCA(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    jmp(a, dep[a]-dep[b]);
    if(a == b) return a;
    for(int k = 20; k >= 0; k--) {
        if(anc[a][k] != anc[b][k]) {
            a = anc[a][k];
            b = anc[b][k];
        }
    }
    return anc[a][0];
}

int getMinimumFuelCapacity(int X, int Y) {
    int l = LCA(X, Y);
    if(pos[l]) return w[l];
    for(int k = 0; k <= 20; k++) {
        if(mx[l][k] != 0) return mx[l][k];
    }
    return -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