제출 #764517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764517		Kihihihi	자매 도시 (APIO20_swap)	C++17	13 / 100	567 ms	44392 KiB

swap

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
#include "swap.h"
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 19;
const long double EPS = 1e-9, PI = acos(-1);

struct dsu
{
    int n;
    vector<int> p, rk, deg, res;

    dsu() {}

    dsu(int in)
    {
        n = in;
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        rk.resize(n);
        deg.resize(n);
        res.resize(n, INF);
    }

    int rt(int v)
    {
        return (p[v] == v ? v : rt(p[v]));
    }

    bool unite(int a, int b, int idx)
    {
        deg[a]++;
        deg[b]++;
        bool thr = (deg[a] >= 3 || deg[b] >= 3);
        a = rt(a);
        b = rt(b);
        if (a == b)
        {
            res[a] = min(res[a], idx);
            return false;
        }

        if (rk[a] < rk[b])
        {
            swap(a, b);
        }
        p[b] = a;
        rk[a] += (rk[a] == rk[b]);
        if (thr)
        {
            res[a] = min(res[a], idx);
            res[b] = min(res[b], idx);
        }
        return true;
    }

    int get(int v)
    {
        int ret = res[v];
        while (p[v] != v)
        {
            v = p[v];
            ret = min(ret, res[v]);
        }
        return ret;
    }
};

struct edge
{
    int to, idx;
};

const int N = 1e5 + 5;

int n, m;
vector<edge> g[N];
vector<int> binup[N], maxidx[N], h;
vector<int> ew;
dsu kek;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N;
    m = M;
    vector<tuple<int, int, int>> e;
    e.resize(m);
    for (int i = 0; i < m; i++)
    {
        e[i] = { W[i], U[i], V[i] };
    }
    sort(e.begin(), e.end());

    ew.resize(m);
    for (int i = 0; i < m; i++)
    {
        ew[i] = get<0>(e[i]);
    }

    kek = dsu(n);
    for (int i = 0; i < m; i++)
    {
        auto& [w, a, b] = e[i];
        if (kek.unite(a, b, i))
        {
            g[a].push_back({ b, i });
            g[b].push_back({ a, i });
        }
    }
    fill_n(binup, n, vector<int>(LOG));
    fill_n(maxidx, n, vector<int>(LOG, INF));
    h.resize(n);

    auto build = [&](auto build, int v, int p) -> void
    {
        if (p == -1)
        {
            h[v] = 0;
            binup[v][0] = 0;
            maxidx[v][0] = -1;
        }
        else
        {
            h[v] = h[p] + 1;
            binup[v][0] = p;
        }

        for (int i = 1; i < LOG; i++)
        {
            binup[v][i] = binup[binup[v][i - 1]][i - 1];
            maxidx[v][i] = max(maxidx[v][i - 1], maxidx[binup[v][i - 1]][i - 1]);
        }

        for (auto& i : g[v])
        {
            if (i.to == p)
            {
                continue;
            }

            maxidx[i.to][0] = i.idx;
            build(build, i.to, v);
        }
    };

    build(build, 0, -1);
}

int getMinimumFuelCapacity(int X, int Y)
{
    auto get_la = [&](int v, int x) -> int
    {
        for (int i = LOG - 1; i > -1; i--)
        {
            if (h[v] - h[binup[v][i]] <= x)
            {
                x -= h[v] - h[binup[v][i]];
                v = binup[v][i];
            }
        }
        return v;
    };

    auto get_lca = [&](int a, int b) -> int
    {
        if (h[a] < h[b])
        {
            swap(a, b);
        }

        a = get_la(a, h[a] - h[b]);
        if (a == b)
        {
            return a;
        }

        for (int i = LOG - 1; i > -1; i--)
        {
            if (binup[a][i] != binup[b][i])
            {
                a = binup[a][i];
                b = binup[b][i];
            }
        }
        return binup[a][0];
    };

    int a = X, b = Y, c = get_lca(a, b);
    int ans = -1;
    int fuck = min(kek.get(a), kek.get(b));
        
    auto get_up = [&](int& ver) -> void
    {
        for (int i = LOG - 1; i > -1; i--)
        {
            if (h[binup[ver][i]] >= h[c])
            {
                ans = max(ans, maxidx[ver][i]);
                ver = binup[ver][i];
            }
        }
    };

    get_up(a);
    get_up(b);

    ans = max(ans, fuck);
    if (ans == INF)
    {
        return -1;
    }
    return ew[ans];
}

/*
int main() {
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));

    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == scanf("%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);

    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        printf("%d\n", minimum_fuel_capacities[i]);
    }

    return 0;
}
*/

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

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