oj.uz

Submission #764524

# Submission time Handle Problem Language Result Execution time Memory
764524 2023-06-23T14:28:10 Z Kihihihi Swapping Cities (APIO20_swap) C++17
13 / 100
 487 ms 44340 KB 
#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);
        }
        if (res[b] != INF)
        {
            res[a] = min(res[a], idx);
        }
        if (res[a] != INF)
        {
            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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7348 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7624 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7620 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 111 ms 32396 KB Output is correct
10 Correct 132 ms 38568 KB Output is correct
11 Correct 149 ms 37896 KB Output is correct
12 Correct 155 ms 39492 KB Output is correct
13 Correct 144 ms 40012 KB Output is correct
14 Correct 131 ms 32364 KB Output is correct
15 Correct 460 ms 41104 KB Output is correct
16 Correct 487 ms 40904 KB Output is correct
17 Correct 443 ms 44340 KB Output is correct
18 Correct 450 ms 43840 KB Output is correct
19 Correct 125 ms 17448 KB Output is correct
20 Correct 464 ms 42444 KB Output is correct
21 Correct 417 ms 41280 KB Output is correct
22 Correct 481 ms 43528 KB Output is correct
23 Correct 427 ms 43748 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7348 KB Output is correct
3 Correct 236 ms 40112 KB Output is correct
4 Correct 219 ms 41352 KB Output is correct
5 Correct 246 ms 40768 KB Output is correct
6 Correct 225 ms 41124 KB Output is correct
7 Correct 256 ms 41160 KB Output is correct
8 Correct 219 ms 36480 KB Output is correct
9 Correct 217 ms 40780 KB Output is correct
10 Correct 227 ms 39476 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7348 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7624 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7620 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 4 ms 7636 KB Output is correct
12 Correct 4 ms 7624 KB Output is correct
13 Correct 4 ms 7508 KB Output is correct
14 Correct 4 ms 7508 KB Output is correct
15 Incorrect 4 ms 7636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7348 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7624 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7620 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 111 ms 32396 KB Output is correct
11 Correct 132 ms 38568 KB Output is correct
12 Correct 149 ms 37896 KB Output is correct
13 Correct 155 ms 39492 KB Output is correct
14 Correct 144 ms 40012 KB Output is correct
15 Correct 4 ms 7636 KB Output is correct
16 Correct 4 ms 7636 KB Output is correct
17 Correct 4 ms 7624 KB Output is correct
18 Correct 4 ms 7508 KB Output is correct
19 Correct 4 ms 7508 KB Output is correct
20 Incorrect 4 ms 7636 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7348 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7624 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7620 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 111 ms 32396 KB Output is correct
10 Correct 132 ms 38568 KB Output is correct
11 Correct 149 ms 37896 KB Output is correct
12 Correct 155 ms 39492 KB Output is correct
13 Correct 144 ms 40012 KB Output is correct
14 Correct 131 ms 32364 KB Output is correct
15 Correct 460 ms 41104 KB Output is correct
16 Correct 487 ms 40904 KB Output is correct
17 Correct 443 ms 44340 KB Output is correct
18 Correct 450 ms 43840 KB Output is correct
19 Correct 236 ms 40112 KB Output is correct
20 Correct 219 ms 41352 KB Output is correct
21 Correct 246 ms 40768 KB Output is correct
22 Correct 225 ms 41124 KB Output is correct
23 Correct 256 ms 41160 KB Output is correct
24 Correct 219 ms 36480 KB Output is correct
25 Correct 217 ms 40780 KB Output is correct
26 Correct 227 ms 39476 KB Output is correct
27 Correct 4 ms 7636 KB Output is correct
28 Correct 4 ms 7636 KB Output is correct
29 Correct 4 ms 7624 KB Output is correct
30 Correct 4 ms 7508 KB Output is correct
31 Correct 4 ms 7508 KB Output is correct
32 Incorrect 4 ms 7636 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7348 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 4 ms 7624 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7620 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 111 ms 32396 KB Output is correct
11 Correct 132 ms 38568 KB Output is correct
12 Correct 149 ms 37896 KB Output is correct
13 Correct 155 ms 39492 KB Output is correct
14 Correct 144 ms 40012 KB Output is correct
15 Correct 131 ms 32364 KB Output is correct
16 Correct 460 ms 41104 KB Output is correct
17 Correct 487 ms 40904 KB Output is correct
18 Correct 443 ms 44340 KB Output is correct
19 Correct 450 ms 43840 KB Output is correct
20 Correct 236 ms 40112 KB Output is correct
21 Correct 219 ms 41352 KB Output is correct
22 Correct 246 ms 40768 KB Output is correct
23 Correct 225 ms 41124 KB Output is correct
24 Correct 256 ms 41160 KB Output is correct
25 Correct 219 ms 36480 KB Output is correct
26 Correct 217 ms 40780 KB Output is correct
27 Correct 227 ms 39476 KB Output is correct
28 Correct 4 ms 7636 KB Output is correct
29 Correct 4 ms 7636 KB Output is correct
30 Correct 4 ms 7624 KB Output is correct
31 Correct 4 ms 7508 KB Output is correct
32 Correct 4 ms 7508 KB Output is correct
33 Incorrect 4 ms 7636 KB Output isn't correct
34 Halted 0 ms 0 KB -