Submission #297231

#	Time	Username	Problem	Language	Result	Execution time	Memory
297231		PeppaPig	Swapping Cities (APIO20_swap)	C++14	100 / 100	623 ms	61876 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

#define iii tuple<int, int, int>

using namespace std;

const int N = 3e5 + 5;

int dsu[N];

int find(int x) { return dsu[x] = x == dsu[x] ? x : find(dsu[x]); }

int n, m, ptr;
int cost[N], deg[N], has_3[N], has_cycle[N], par[N][20], dep[N];
vector<int> g[N];

void onion(int a, int b) {
    has_3[ptr] = has_3[find(a)] | has_3[find(b)]; 
    has_cycle[ptr] = has_cycle[find(a)] | has_cycle[find(b)]; 

    if(deg[a] >= 3 || deg[b] >= 3) has_3[ptr] = 1;

    g[ptr].emplace_back(find(a));
    if(find(a) == find(b)) has_cycle[ptr] = 1;
    else g[ptr].emplace_back(find(b));

    dsu[find(a)] = dsu[find(b)] = ptr;
}

void dfs(int u, int p) {
    dep[u] = dep[p] + 1, par[u][0] = p;
    for(int i = 1; i <= 19; i++) par[u][i] = par[par[u][i - 1]][i - 1];
    for(int v : g[u]) {
        dfs(v, u);
        has_3[u] |= has_3[v], has_cycle[u] |= has_cycle[v];
    }
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 19; ~i; i--) if(dep[par[a][i]] >= dep[b]) a = par[a][i];
    if(a == b) return a;
    for(int i = 19; ~i; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
    return par[a][0];
}

void init(int _n, int _m, vector<int> U, vector<int> V, vector<int> W) {
    n = ptr = _n, m = _m;
    iota(dsu, dsu + N, 0);

    vector<iii> E;
    for(int i = 0; i < m; i++) E.emplace_back(W[i], ++U[i], ++V[i]);

    sort(E.begin(), E.end());
    for(int i = 0; i < m; i++) {
        int u, v, w; tie(w, u, v) = E[i];
        cost[++ptr] = w, ++deg[u], ++deg[v];
        onion(u, v);
    }
    cost[0] = -1, has_3[0] = has_cycle[0] = 1;
    dfs(ptr, 0);
}

int getMinimumFuelCapacity(int a, int b) {
    int l = lca(++a, ++b);

    if(has_3[l] || has_cycle[l]) return cost[l];
    for(int i = 19; ~i; i--) if(!has_3[par[l][i]] && !has_cycle[par[l][i]])
        l = par[l][i];
    return cost[par[l][0]];
}

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