Submission #1190782

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

swap

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

int N, M;
int l = 20;
int timer;
vector<vector<pair<int, int>>> edge;
vector<int> tin, tout, cost;
vector<vector<int>> ancestor, max_weight;

void dfs (int v, int p) {
    tin[v] = timer++;
    ancestor[v][0] = p;

    for (int i = 1; i <= l; 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 u : edge[v]) {
        if (u.first != p) {
            max_weight[u.first][0] = u.second;
            ancestor[u.first][0] = v;
            dfs(u.first, v);
        }
    }

    tout[v] = timer++;
}

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

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

int max_w(int u, int LCA) {
    if (u == LCA) {return 0;}
    int i = l;
    int m = 0;
    while (ancestor[u][0] != LCA) {
        if (!is_ancestor(ancestor[u][i], LCA)) {
            m = max(m, max_weight[u][i]);
            u = ancestor[u][i];
        }
        i --;
    }
    m = max(m, max_weight[u][0]);
    return m;
}

void preprocess (int root) {
    tin.resize(N);
    tout.resize(N);
    timer = 0;
    ancestor.resize(N, vector<int>(l+1));
    max_weight.resize(N, vector<int>(l+1, 0));
    dfs(root, root);
}

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

    cost.resize(n+1, 1e9);
    for (int i = 0; i < n; i ++) {
        if (edge[i].size() >= 3) {
            int min1 = 1e9, min2 = 1e9, min3 = 1e9;
            for (auto j : edge[i]) {
                if (j.first <= min1) {
                    min3 = min2;
                    min2 = min1;
                    min1 = j.first;
                }
                else if (j.first <= min2) {
                    min3 = min2;
                    min2 = j.first;
                }
                else if (j.first <= min3) {
                    min3 = j.first;
                }
            }
            cost[i] = min3;
        }
    }

    for (int i = 0; i < m; i ++) {
        int a = u[i], b = v[i], c = w[i];
        cost[a] = min(cost[a], max(cost[b], c));
        cost[b] = min(cost[b], max(cost[a], c));
    }
    
    N = n;
    M = m;
    preprocess(0);
}

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 ans = max(path_max_w, cost[x]);
    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