제출 #1191149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191149		zh_h	Swapping Cities (APIO20_swap)	C++17	30 / 100	2073 ms	589824 KiB

swap

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

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

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;
            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;
    l = ceil(log2(N));
    ancestor.resize(N, vector<int>(l+1));
    max_weight.resize(N, vector<int>(l+1, 0));
    dfs(root, root);
}

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

    if (edge[v].size() >= 3) {
        sort(edge[v].begin(), edge[v].end(), [](pair<int, int> a, pair<int, int> b){
            return a.second < b.second;
        });
        cost[v] = edge[v][2].second;
    }

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

}

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


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);
    
    N = n;
    M = m;
    preprocess(0);
    preprocess_cost(0, -1);
    preprocess_cost2(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 ans = max(path_max_w, cost[x]);
    if (ans >= 1e9) {ans = -1;}

    return ans;
}

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