oj.uz

Submission #969716

# Submission time Handle Problem Language Result Execution time Memory
969716 2024-04-25T13:35:10 Z LOLOLO Swapping Cities (APIO20_swap) C++17
100 / 100
 507 ms 66216 KB 
#include <bits/stdc++.h>
//#include "swap.h"
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 50;

struct dsu{
    vector <int> sz, par, line, cost, st, en, degree;
    vector < vector <int>> in, p, cc;
    vector < vector <pair <int, int>>> ed;
    int dfstimer = 1;

    void prepare(int n) {
        sz.assign(n + 1, 1);
        par.assign(n + 1, 0);
        line.assign(n + 1, 1);
        cost.assign(n + 1, 1e9 + 10);
        st.assign(n + 1, 0);
        en.assign(n + 1, 0);
        degree.assign(n + 1, 0);
        in.resize(n + 1);
        ed.resize(n + 1);

        for (int i = 0; i <= n; i++) {
            in[i].pb(i);
            p.pb(vector <int> (20, 0));
            cc.pb(vector <int> (20, 0));
        }
    }

    int get(int a) {
        return par[a] ? get(par[a]) : a;
    }

    void dfs(int u, int v) {
        st[u] = ++dfstimer;
        p[u][0] = v;

        for (int j = 1; j < 20; j++) {
            p[u][j] = p[p[u][j - 1]][j - 1];
            cc[u][j] = max(cc[u][j - 1], cc[p[u][j - 1]][j - 1]);
        }

        for (auto x : ed[u]) {
            if (x.f == v)
                continue;

            cc[x.f][0] = x.s;
            dfs(x.f, u);
        }

        en[u] = dfstimer;
    }

    bool is(int a, int b) {
        return st[a] <= st[b] && en[a] >= en[b];
    }

    int lca(int a, int b) {
        if (is(a, b))
            return a;

        if (is(b, a))
            return b;

        for (int j = 19; j >= 0; j--) {
            if (is(p[a][j], b) == 0)
                a = p[a][j];
        }

        return p[a][0];
    }

    int answer(int a, int b) {
        int c = lca(a, b), ans = max(cost[a], cost[b]);
        for (int j = 19; j >= 0; j--) {
            if (is(c, p[a][j])) {
                ans = max(ans, cc[a][j]);
                a = p[a][j];
            }

            if (is(c, p[b][j])) {
                ans = max(ans, cc[b][j]);
                b = p[b][j];
            }
        }

        return ans;
    }

    void unite(int a, int b, int w) {
        int x = a, y = b;
        degree[a]++;
        degree[b]++;
        int mx = max(degree[a], degree[b]);
        a = get(a), b = get(b);
        if (a == b) {
            line[a] = 0;
            for (auto x : in[a]) {
                cost[x] = w;
            }

            in[a].clear();
            return;
        }

        ed[x].pb({y, w});
        ed[y].pb({x, w});
        if (sz[a] < sz[b])
            swap(a, b);

        sz[a] += sz[b];
        par[b] = a;
        line[a] = line[a] & line[b];

        if (mx > 2) {
            line[a] = 0; 
        }

        for (auto x : in[b])
            in[a].pb(x);

        if (line[a] == 0) {
            for (auto x : in[a]) {
                cost[x] = w;
            }
            in[a].clear();
        }
    }
} D;

void init(int n, int m, vector <int> u, vector <int> v, vector <int> w) {
    dsu D1;
    D = D1;
    D.prepare(n);
    vector < vector <int>> edge;
    for (int i = 0; i < m; i++) {
        edge.pb({w[i], u[i] + 1, v[i] + 1});
    }

    sort(all(edge));
    for (auto x : edge) {
        D.unite(x[1], x[2], x[0]);
    }

    D.dfs(1, 1);
}

int getMinimumFuelCapacity(int a, int b) {
    a++;
    b++;
    int ans = D.answer(a, b);
    if (ans > 1e9)
        return -1;

    return ans;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
--------------------------------------------------|
3 2
0 1 5
0 2 5
1
1 2
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
3
10
4
--------------------------------------------------|
-1
--------------------------------------------------|
==================================================+
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 171 ms 42692 KB Output is correct
10 Correct 209 ms 49328 KB Output is correct
11 Correct 206 ms 50176 KB Output is correct
12 Correct 247 ms 52144 KB Output is correct
13 Correct 199 ms 50180 KB Output is correct
14 Correct 184 ms 40280 KB Output is correct
15 Correct 478 ms 51888 KB Output is correct
16 Correct 424 ms 49776 KB Output is correct
17 Correct 506 ms 54188 KB Output is correct
18 Correct 448 ms 51376 KB Output is correct
19 Correct 98 ms 11348 KB Output is correct
20 Correct 401 ms 51924 KB Output is correct
21 Correct 415 ms 49280 KB Output is correct
22 Correct 447 ms 54188 KB Output is correct
23 Correct 426 ms 51552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 254 ms 45236 KB Output is correct
4 Correct 253 ms 47540 KB Output is correct
5 Correct 246 ms 46460 KB Output is correct
6 Correct 243 ms 47912 KB Output is correct
7 Correct 240 ms 47228 KB Output is correct
8 Correct 261 ms 46108 KB Output is correct
9 Correct 245 ms 46516 KB Output is correct
10 Correct 240 ms 44624 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 1 ms 908 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 171 ms 42692 KB Output is correct
11 Correct 209 ms 49328 KB Output is correct
12 Correct 206 ms 50176 KB Output is correct
13 Correct 247 ms 52144 KB Output is correct
14 Correct 199 ms 50180 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 1 ms 856 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 1108 KB Output is correct
21 Correct 2 ms 856 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 908 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 2 ms 860 KB Output is correct
34 Correct 14 ms 6864 KB Output is correct
35 Correct 226 ms 52040 KB Output is correct
36 Correct 231 ms 50828 KB Output is correct
37 Correct 226 ms 49868 KB Output is correct
38 Correct 201 ms 48044 KB Output is correct
39 Correct 172 ms 47536 KB Output is correct
40 Correct 163 ms 43360 KB Output is correct
41 Correct 229 ms 52320 KB Output is correct
42 Correct 222 ms 53756 KB Output is correct
43 Correct 221 ms 50728 KB Output is correct
44 Correct 169 ms 48800 KB Output is correct
45 Correct 160 ms 47040 KB Output is correct
46 Correct 241 ms 51372 KB Output is correct
47 Correct 182 ms 48132 KB Output is correct
48 Correct 170 ms 47840 KB Output is correct
49 Correct 78 ms 18332 KB Output is correct
50 Correct 64 ms 14980 KB Output is correct
51 Correct 130 ms 37300 KB Output is correct
52 Correct 266 ms 58108 KB Output is correct
53 Correct 244 ms 58540 KB Output is correct
54 Correct 280 ms 62632 KB Output is correct
55 Correct 185 ms 50608 KB Output is correct
56 Correct 211 ms 56940 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 171 ms 42692 KB Output is correct
10 Correct 209 ms 49328 KB Output is correct
11 Correct 206 ms 50176 KB Output is correct
12 Correct 247 ms 52144 KB Output is correct
13 Correct 199 ms 50180 KB Output is correct
14 Correct 184 ms 40280 KB Output is correct
15 Correct 478 ms 51888 KB Output is correct
16 Correct 424 ms 49776 KB Output is correct
17 Correct 506 ms 54188 KB Output is correct
18 Correct 448 ms 51376 KB Output is correct
19 Correct 254 ms 45236 KB Output is correct
20 Correct 253 ms 47540 KB Output is correct
21 Correct 246 ms 46460 KB Output is correct
22 Correct 243 ms 47912 KB Output is correct
23 Correct 240 ms 47228 KB Output is correct
24 Correct 261 ms 46108 KB Output is correct
25 Correct 245 ms 46516 KB Output is correct
26 Correct 240 ms 44624 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 856 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 1108 KB Output is correct
33 Correct 2 ms 856 KB Output is correct
34 Correct 1 ms 860 KB Output is correct
35 Correct 1 ms 908 KB Output is correct
36 Correct 14 ms 6864 KB Output is correct
37 Correct 226 ms 52040 KB Output is correct
38 Correct 231 ms 50828 KB Output is correct
39 Correct 226 ms 49868 KB Output is correct
40 Correct 201 ms 48044 KB Output is correct
41 Correct 172 ms 47536 KB Output is correct
42 Correct 163 ms 43360 KB Output is correct
43 Correct 229 ms 52320 KB Output is correct
44 Correct 222 ms 53756 KB Output is correct
45 Correct 221 ms 50728 KB Output is correct
46 Correct 169 ms 48800 KB Output is correct
47 Correct 22 ms 6608 KB Output is correct
48 Correct 430 ms 55864 KB Output is correct
49 Correct 472 ms 54108 KB Output is correct
50 Correct 425 ms 54004 KB Output is correct
51 Correct 427 ms 52148 KB Output is correct
52 Correct 336 ms 49076 KB Output is correct
53 Correct 231 ms 37096 KB Output is correct
54 Correct 431 ms 56096 KB Output is correct
55 Correct 491 ms 57520 KB Output is correct
56 Correct 385 ms 53956 KB Output is correct
57 Correct 374 ms 52272 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 171 ms 42692 KB Output is correct
11 Correct 209 ms 49328 KB Output is correct
12 Correct 206 ms 50176 KB Output is correct
13 Correct 247 ms 52144 KB Output is correct
14 Correct 199 ms 50180 KB Output is correct
15 Correct 184 ms 40280 KB Output is correct
16 Correct 478 ms 51888 KB Output is correct
17 Correct 424 ms 49776 KB Output is correct
18 Correct 506 ms 54188 KB Output is correct
19 Correct 448 ms 51376 KB Output is correct
20 Correct 254 ms 45236 KB Output is correct
21 Correct 253 ms 47540 KB Output is correct
22 Correct 246 ms 46460 KB Output is correct
23 Correct 243 ms 47912 KB Output is correct
24 Correct 240 ms 47228 KB Output is correct
25 Correct 261 ms 46108 KB Output is correct
26 Correct 245 ms 46516 KB Output is correct
27 Correct 240 ms 44624 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 856 KB Output is correct
30 Correct 1 ms 856 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 1108 KB Output is correct
34 Correct 2 ms 856 KB Output is correct
35 Correct 1 ms 860 KB Output is correct
36 Correct 1 ms 908 KB Output is correct
37 Correct 14 ms 6864 KB Output is correct
38 Correct 226 ms 52040 KB Output is correct
39 Correct 231 ms 50828 KB Output is correct
40 Correct 226 ms 49868 KB Output is correct
41 Correct 201 ms 48044 KB Output is correct
42 Correct 172 ms 47536 KB Output is correct
43 Correct 163 ms 43360 KB Output is correct
44 Correct 229 ms 52320 KB Output is correct
45 Correct 222 ms 53756 KB Output is correct
46 Correct 221 ms 50728 KB Output is correct
47 Correct 169 ms 48800 KB Output is correct
48 Correct 22 ms 6608 KB Output is correct
49 Correct 430 ms 55864 KB Output is correct
50 Correct 472 ms 54108 KB Output is correct
51 Correct 425 ms 54004 KB Output is correct
52 Correct 427 ms 52148 KB Output is correct
53 Correct 336 ms 49076 KB Output is correct
54 Correct 231 ms 37096 KB Output is correct
55 Correct 431 ms 56096 KB Output is correct
56 Correct 491 ms 57520 KB Output is correct
57 Correct 385 ms 53956 KB Output is correct
58 Correct 374 ms 52272 KB Output is correct
59 Correct 98 ms 11348 KB Output is correct
60 Correct 401 ms 51924 KB Output is correct
61 Correct 415 ms 49280 KB Output is correct
62 Correct 447 ms 54188 KB Output is correct
63 Correct 426 ms 51552 KB Output is correct
64 Correct 1 ms 604 KB Output is correct
65 Correct 1 ms 860 KB Output is correct
66 Correct 1 ms 860 KB Output is correct
67 Correct 1 ms 604 KB Output is correct
68 Correct 1 ms 604 KB Output is correct
69 Correct 2 ms 860 KB Output is correct
70 Correct 2 ms 860 KB Output is correct
71 Correct 2 ms 860 KB Output is correct
72 Correct 1 ms 860 KB Output is correct
73 Correct 2 ms 860 KB Output is correct
74 Correct 160 ms 47040 KB Output is correct
75 Correct 241 ms 51372 KB Output is correct
76 Correct 182 ms 48132 KB Output is correct
77 Correct 170 ms 47840 KB Output is correct
78 Correct 78 ms 18332 KB Output is correct
79 Correct 64 ms 14980 KB Output is correct
80 Correct 130 ms 37300 KB Output is correct
81 Correct 266 ms 58108 KB Output is correct
82 Correct 244 ms 58540 KB Output is correct
83 Correct 280 ms 62632 KB Output is correct
84 Correct 185 ms 50608 KB Output is correct
85 Correct 211 ms 56940 KB Output is correct
86 Correct 76 ms 17856 KB Output is correct
87 Correct 444 ms 54456 KB Output is correct
88 Correct 459 ms 53996 KB Output is correct
89 Correct 284 ms 49840 KB Output is correct
90 Correct 150 ms 22768 KB Output is correct
91 Correct 172 ms 24640 KB Output is correct
92 Correct 254 ms 40624 KB Output is correct
93 Correct 500 ms 61252 KB Output is correct
94 Correct 384 ms 61360 KB Output is correct
95 Correct 507 ms 66216 KB Output is correct
96 Correct 396 ms 53648 KB Output is correct
97 Correct 344 ms 57000 KB Output is correct