oj.uz

Submission #764517

# Submission time Handle Problem Language Result Execution time Memory
764517 2023-06-23T14:09:28 Z Kihihihi Swapping Cities (APIO20_swap) C++17
13 / 100
 567 ms 44392 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);
        }
        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 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7348 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7636 KB Output is correct
6 Correct 4 ms 7588 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 4 ms 7620 KB Output is correct
9 Correct 101 ms 32412 KB Output is correct
10 Correct 143 ms 38548 KB Output is correct
11 Correct 130 ms 37912 KB Output is correct
12 Correct 170 ms 39816 KB Output is correct
13 Correct 140 ms 40552 KB Output is correct
14 Correct 132 ms 32464 KB Output is correct
15 Correct 459 ms 42508 KB Output is correct
16 Correct 510 ms 40936 KB Output is correct
17 Correct 448 ms 44392 KB Output is correct
18 Correct 446 ms 43856 KB Output is correct
19 Correct 122 ms 17416 KB Output is correct
20 Correct 459 ms 42460 KB Output is correct
21 Correct 452 ms 41284 KB Output is correct
22 Correct 567 ms 43832 KB Output is correct
23 Correct 489 ms 44040 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 230 ms 40044 KB Output is correct
4 Correct 235 ms 41384 KB Output is correct
5 Correct 232 ms 40764 KB Output is correct
6 Correct 236 ms 41212 KB Output is correct
7 Correct 244 ms 41176 KB Output is correct
8 Correct 216 ms 39860 KB Output is correct
9 Correct 229 ms 40780 KB Output is correct
10 Correct 227 ms 39652 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7348 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7636 KB Output is correct
7 Correct 4 ms 7588 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 4 ms 7620 KB Output is correct
10 Correct 101 ms 32412 KB Output is correct
11 Correct 143 ms 38548 KB Output is correct
12 Correct 130 ms 37912 KB Output is correct
13 Correct 170 ms 39816 KB Output is correct
14 Correct 140 ms 40552 KB Output is correct
15 Correct 4 ms 7620 KB Output is correct
16 Incorrect 4 ms 7636 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7348 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7636 KB Output is correct
6 Correct 4 ms 7588 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 4 ms 7620 KB Output is correct
9 Correct 101 ms 32412 KB Output is correct
10 Correct 143 ms 38548 KB Output is correct
11 Correct 130 ms 37912 KB Output is correct
12 Correct 170 ms 39816 KB Output is correct
13 Correct 140 ms 40552 KB Output is correct
14 Correct 132 ms 32464 KB Output is correct
15 Correct 459 ms 42508 KB Output is correct
16 Correct 510 ms 40936 KB Output is correct
17 Correct 448 ms 44392 KB Output is correct
18 Correct 446 ms 43856 KB Output is correct
19 Correct 230 ms 40044 KB Output is correct
20 Correct 235 ms 41384 KB Output is correct
21 Correct 232 ms 40764 KB Output is correct
22 Correct 236 ms 41212 KB Output is correct
23 Correct 244 ms 41176 KB Output is correct
24 Correct 216 ms 39860 KB Output is correct
25 Correct 229 ms 40780 KB Output is correct
26 Correct 227 ms 39652 KB Output is correct
27 Correct 4 ms 7620 KB Output is correct
28 Incorrect 4 ms 7636 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7348 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7636 KB Output is correct
7 Correct 4 ms 7588 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 4 ms 7620 KB Output is correct
10 Correct 101 ms 32412 KB Output is correct
11 Correct 143 ms 38548 KB Output is correct
12 Correct 130 ms 37912 KB Output is correct
13 Correct 170 ms 39816 KB Output is correct
14 Correct 140 ms 40552 KB Output is correct
15 Correct 132 ms 32464 KB Output is correct
16 Correct 459 ms 42508 KB Output is correct
17 Correct 510 ms 40936 KB Output is correct
18 Correct 448 ms 44392 KB Output is correct
19 Correct 446 ms 43856 KB Output is correct
20 Correct 230 ms 40044 KB Output is correct
21 Correct 235 ms 41384 KB Output is correct
22 Correct 232 ms 40764 KB Output is correct
23 Correct 236 ms 41212 KB Output is correct
24 Correct 244 ms 41176 KB Output is correct
25 Correct 216 ms 39860 KB Output is correct
26 Correct 229 ms 40780 KB Output is correct
27 Correct 227 ms 39652 KB Output is correct
28 Correct 4 ms 7620 KB Output is correct
29 Incorrect 4 ms 7636 KB Output isn't correct
30 Halted 0 ms 0 KB -