제출 #984411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984411		vjudge2	자매 도시 (APIO20_swap)	C++17	0 / 100	61 ms	47964 KiB

swap

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

const int N = 300005;
const int lg = 19;

int id, deg[N], ans[N], one[N], three[N], p[N], dep[N];
vector<int> adj[N];
vector<vector<int>> lift(N, vector<int> (lg));

int find(int u) {
    return p[u] == u ? u : find(p[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    p[v] = u;
    one[u] += one[v];
    three[u] += three[v];
}

void dfs(int u) {
    for (int v : adj[u]) {
        if (!ans[v]) ans[v] = ans[u];
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}

int jump(int s, int d) {
    for (int i = lg - 1; i >= 0; i--) if (d & (1 << i)) s = lift[s][i];
    return s;
}

int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    v = jump(v, dep[v] - dep[u]);
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--) {
        int ut = lift[u][i], vt = lift[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return lift[u][0];
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    vector<array<int, 3>> e;
    for (int i = 0; i < m; i++) e.push_back({w[i], u[i], v[i]});
    sort(e.begin(), e.end());
    for (int i = 0; i < N; i++) p[i] = i;
    id = n - 1;
    for (auto& [w, u, v] : e) {
        if (deg[u] == 1) one[find(u)]--;
        if (deg[v] == 1) one[find(v)]--;
        deg[u]++, deg[v]++;
        if (deg[u] == 1) one[find(u)]++;
        else if (deg[u] == 3) three[find(u)]++;
        if (deg[v] == 1) one[find(v)]++;
        else if (deg[v] == 3) three[find(v)]++;
        u = find(u), v = find(v);
        id++;
        if (u == v) {
            merge(id, u);
            lift[u][0] = id;
            adj[id].push_back(u);
            // cout << id << " --> " << u << '\n';
        } else {
            merge(id, u);
            merge(id, v);
            lift[u][0] = lift[v][0] = id;
            adj[id].push_back(u);
            // cout << id << " --> " << u << '\n';
            adj[id].push_back(v);
            // cout << id << " --> " << v << '\n';
        }
        if (three[id]) ans[id] = w;
        else if (!one[id]) ans[id] = w;
        // cout << "value @ " << id << " = " << w << '\n';
    }
    for (int i = 0; i < N; i++) if (find(i) == i) lift[i][0] = i, dfs(i);
    for (int j = 1; j < lg; j++) for (int i = 0; i < N; i++) {
        lift[i][j] = lift[lift[i][j - 1]][j - 1];
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if (find(X) != find(Y)) return -1;
    // cout << lca(X, Y) << '\n';
    return ans[lca(X, Y)];
}

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