제출 #1246940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246940		Turkhuu	Swapping Cities (APIO20_swap)	C++20	13 / 100	443 ms	56316 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
int N, M, lgNM, timer;
vector<int> edge_cnt, node_cnt, l, r, p, w, lvl;
vector<vector<int>> par, spt, ch;
int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
int qry(int l, int r) {
    int k = __lg(r - l);
    return min(spt[k][l], spt[k][r - (1 << k)]);
}
void dfs(int x) {
    (x < N ? node_cnt : edge_cnt)[x]++;
    for (int i = 0; i < lgNM && par[x][i] != -1; i++)
        par[x][i + 1] = par[par[x][i]][i];
    l[x] = timer;
    if (x < N) timer++;
    for (int y : ch[x]) {
        par[y][0] = x;
        lvl[y] = lvl[x] + 1;
        dfs(y);
        node_cnt[x] += node_cnt[y];
        edge_cnt[x] += edge_cnt[y];
    }
    r[x] = timer;
}
int lca(int x, int y) {
    if (lvl[x] < lvl[y]) swap(x, y);
    FOR(i, 0, lgNM) if ((lvl[x] - lvl[y]) >> i & 1) x = par[x][i];
    if (x == y) return x;
    ROF(i, lgNM, 0) if (par[x][i] != par[y][i]) x = par[x][i], y = par[y][i];
    return par[x][0];
}
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    N = _N, M = _M; int lgN = __lg(N); lgNM = __lg(N + M);
    l.resize(N + M);
    r.resize(N + M);
    w.resize(N + M);
    p.resize(N + M); iota(p.begin(), p.end(), 0);
    ch.resize(N + M);
    lvl.resize(N + M);
    edge_cnt.resize(N + M);
    node_cnt.resize(N + M);
    par.resize(N + M, vector<int>(lgNM + 1, -1));
    spt.resize(lgN + 1); spt[0].resize(N);
    vector<int> ord(M), deg(N), t(N, 2e9);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {return W[i] < W[j];});
    FOR(oi, 0, M - 1) {
        int i = ord[oi], x = U[i], y = V[i];
        if (++deg[x] == 3) t[x] = W[i];
        if (++deg[y] == 3) t[y] = W[i];
        x = find(x), y = find(y);
        ch[N + oi].push_back(x);
        if (x != y) ch[N + oi].push_back(y);
        p[x] = p[y] = N + oi, w[N + oi] = W[i];
    }
    dfs(N + M - 1);
    FOR(i, 0, N - 1) spt[0][l[i]] = t[i];
    FOR(i, 0, lgN - 1) {
        spt[i + 1].resize(N - (2 << i) + 1);
        FOR(j, 0, N - (2 << i)) spt[i + 1][j] = min(spt[i][j], spt[i][j + (1 << i)]);
    }
}
int getMinimumFuelCapacity(int X, int Y) {
    int Z = lca(X, Y), ans = qry(l[Z], r[Z]);
    if (edge_cnt[N + M - 1] >= node_cnt[N + M - 1]) {
        int x = Z;
        if (edge_cnt[x] < node_cnt[x]) {
            ROF(i, lgNM, 0) if (par[x][i] != -1 && edge_cnt[par[x][i]] < node_cnt[par[x][i]]) x = par[x][i];
            x = par[x][0];
        }
        ans = min(ans, w[x]);
    }
    ans = max(ans, w[Z]);
    return ans == 2e9 ? -1 : ans;
}

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