Submission #467356

#	Time	Username	Problem	Language	Result	Execution time	Memory
467356		SirCovidThe19th	Swapping Cities (APIO20_swap)	C++17	100 / 100	446 ms	66628 KiB

swap

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

const int mx = 3e5 + 5;

int node, par[mx], up[mx][19], vals[mx], deg[mx], dep[mx]; 
bool ok[mx][19], cyc[mx], deg3[mx]; vector<int> adj[mx];

int get(int i){
    return i == par[i] ? i : par[i] = get(par[i]);
}
void merge(int A, int B){
    int a = get(A), b = get(B); deg[A]++; deg[B]++;
    deg3[node] = deg[A] == 3 or deg[B] == 3 or deg3[a] or deg3[b];
    cyc[node] = a == b or cyc[a] or cyc[b];
    adj[node].push_back(a); if (a != b) adj[node].push_back(b);
    par[a] = par[b] = node++;
}
void dfs(int i){
    for (int l = 1; l < 19; l++){
        up[i][l] = up[up[i][l - 1]][l - 1];
        ok[i][l] = ok[up[i][l - 1]][l - 1] or ok[i][l - 1];
    }
    for (auto x : adj[i]){
        up[x][0] = i; ok[x][0] = cyc[i] or deg3[i];
        dep[x] = dep[i] + 1; dfs(x);
    }
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    int idx[m]; node = n + 1; iota(idx, idx + m, 0); iota(par, par + n + m + 1, 0); 
    sort(idx, idx + m, [&](int a, int b){ return w[a] < w[b]; });
    for (int i : idx){
        vals[node] = w[i]; 
        merge(u[i] + 1, v[i] + 1);
    }
    for (int i = n + m; i > 0; i--)
        if (!up[i][0]) dfs(i);
}
int getMinimumFuelCapacity(int x, int y){
    x++; y++; if (dep[x] < dep[y]) swap(x, y);
    for (int i = 18; i >= 0; i--)
        if (((dep[x] - dep[y]) >> i) & 1) x = up[x][i];
    auto good = [&](){ return (cyc[x] or deg3[x]) and (cyc[y] or deg3[y]); };
    for (int i = 18; i >= 0; i--)
        if (up[x][i] != up[y][i] or (!ok[x][i] and !ok[y][i] and !good())) 
            x = up[x][i], y = up[y][i];
    int L = (x != y or !good()) ? up[x][0] : x;
    return (!L) ? -1 : vals[L];
}

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