Submission #1191141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191141		zh_h	Swapping Cities (APIO20_swap)	C++17	0 / 100	905 ms	589824 KiB

swap

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

int _n, _m;
int timer;
vector<int> tin, tout, cost;
vector<vector<pair<int, int>>> edge;
vector<vector<int>> ancestor, max_weight;

void dfs (int v, int par) {
    tin[v] = timer++;
    ancestor[v][0] = par;
    for (int i = 1; i <= 19; i ++) {
        ancestor[v][i] = ancestor[ancestor[v][i-1]][i-1];
        max_weight[v][i] = max(max_weight[v][i-1], max_weight[ancestor[v][i-1]][i-1]);
    }

    for (auto [child, w] : edge[v]) {
        if (child == par) continue;
        
        max_weight[child][0] = w;
        dfs(child, v);
    }

    tout[v] = timer++;
}

bool is_ancestor (int child, int p) {
    return tin[child] <= tin[p] && tout[child] >= tout[p];
}

int LCA (int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = 19; i >= 0; i --) {
        if (!is_ancestor(ancestor[u][i], v)) u = ancestor[u][i];
    }

    return ancestor[u][0];
}

int MAX_W (int child, int lca) {
    if (child == lca) {return 0;}
    int m = 0, i = 19;
    while (ancestor[child][0] != lca) {
        if (!is_ancestor(child, ancestor[child][i])) {
            m = max(m, max_weight[child][i]);
            child = ancestor[child][i];
        }
        i--;
    }

    return m;
}

void preprocess (int v) {
    tin.resize(_n); tout.resize(_n);
    timer = 0;
    ancestor.resize(_n, vector<int>(20));
    max_weight.resize(_n, vector<int>(20));
    dfs(v, v);
}

void preprocess_cost (int v, int p) {
    for (auto [child, w] : edge[v]) {
        if (child == p) continue;
        preprocess_cost (child, v);
        cost[child] = min(cost[child], max(cost[v], w));
        cost[v] = min(cost[v], max(cost[child], w));
    }
}

void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    edge.resize(n);
    for (int i = 0; i < m; i ++) {
        edge[u[i]].pb({v[i], w[i]});
        edge[v[i]].pb({u[i], w[i]});
    }

    _n = n; _m = m;

    ancestor.resize(n, vector<int>(20));
    max_weight.resize(n, vector<int>(20));
    preprocess(0);
    
    cost.resize(_n, 1e9);
    preprocess_cost(0, -1);
}

int getMinimumFuelCapacity(int x, int y) {
    int lca = LCA(x, y);
    int path_max_w = max(MAX_W(x, lca), MAX_W(y, lca));
    int extra_cost = cost[x];

    int ans = max(extra_cost, path_max_w);
    if (ans == 1e9) ans = -1;
    return ans;
}

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