oj.uz

Submission #737838

# Submission time Handle Problem Language Result Execution time Memory
737838 2023-05-07T20:04:21 Z Abrar_Al_Samit Swapping Cities (APIO20_swap) C++17
100 / 100
 407 ms 51764 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int nax = 2e5 + 3;
const int INF = 2e9;
const int lg = 18;

vector<tuple<int,int,int>>edges;
int n, m;
int nbe[nax/2], lvl[nax/2], tt = 1, st[nax/2], en[nax/2];
vector<pair<int,int>>g[nax/2];
int sz[nax/2], par[nax/2];
int deg[nax];
int sp[nax/2][lg], mxw[nax/2][lg];
bool bam[nax/2];
vector<int>elem[nax];

int find(int v) {
    return par[v] = (v==par[v]) ? v : find(par[v]);
}
bool same(int u, int v) {
    return find(u) == find(v);
}
void unite(int u, int v, int w) {
    int root_u = find(u), root_v = find(v);
    if(sz[root_u] < sz[root_v]) swap(root_u, root_v), swap(u, v);

    if(bam[root_u] && bam[root_v] && deg[u]<2 && deg[v]<2) {
        deg[u]++, deg[v]++;
        par[root_v] = root_u;
        sz[root_u] += sz[root_v];
        bam[root_u] = true;

        for(int x : elem[root_v]) {
            elem[root_u].push_back(x);
        }
        elem[root_v].clear();

    } else {
        if(bam[root_u]) {
            for(int x : elem[root_u]) {
                nbe[x] = w;
            }
        }
        if(bam[root_v]) {
            for(int x : elem[root_v]) {
                nbe[x] = w;
            }
        }

        for(int x : elem[root_v]) {
            elem[root_u].push_back(x);
        }
        elem[root_v].clear();

        par[root_v] = root_u;
        sz[root_u] += sz[root_v];
        bam[root_u] = false;
    }
}
void makeMST() {
    for(int i=0; i<n; ++i) {
        sz[i] = 1, par[i] = i;
        bam[i] = 1;
        elem[i].push_back(i);
    }

    for(auto [w, u, v] : edges) {
        if(same(u, v)) {
            int root = find(u);
            if(bam[root]) {
                for(int x : elem[root]) {
                    nbe[x] = w;
                }
                bam[root] = false;
            }
        } else {
            unite(u, v, w);
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
    }
}   
void dfs(int v, int p = 0, int topar = 0, int lv = 0) {
    lvl[v] = lv;
    sp[v][0] = p;
    mxw[v][0] = topar;
    st[v] = tt++;

    for(int j=1; j<lg; ++j) {
        sp[v][j] = sp[sp[v][j-1]][j-1];
        mxw[v][j] = max(mxw[v][j-1], mxw[sp[v][j-1]][j-1]);
    }

    for(auto [u, w] : g[v]) if(u!=p) {
        dfs(u, v, w, lv+1);
    }
    en[v] = tt-1;
}

bool is_anc(int u, int v) {
    return st[u] <= st[v] && en[u] >= en[v];
}
int get(int u, int v) {
    int ret = 0;
    for(int j=lg-1; j>=0; --j) {
        if(!is_anc(sp[u][j], v)) {
            ret = max(ret, mxw[u][j]);
            u = sp[u][j];
        }
    }   
    if(!is_anc(u, v)) {
        ret = max(ret, mxw[u][0]);
        u = sp[u][0];
    }

    for(int j=lg-1; j>=0; --j) {
        if(!is_anc(sp[v][j], u)) {
            ret = max(ret, mxw[v][j]);
            v = sp[v][j];
        }
    }
    if(!is_anc(v, u)) {
        ret = max(ret, mxw[v][0]);
        v = sp[v][0];
    }
    return ret;
}
void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {

    n = N, m = M;
    for(int i=0; i<M; ++i) {
        edges.emplace_back(W[i], U[i], V[i]);
    }
    for(int i=0; i<N; ++i) {
        nbe[i] = INF;
    }
    sort(edges.begin(), edges.end());

    makeMST();
    dfs(0);
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans = max({nbe[X], nbe[Y], get(X, Y)});

    if(ans==INF) ans = -1;
    return ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7492 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7628 KB Output is correct
7 Correct 6 ms 7724 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 132 ms 36024 KB Output is correct
10 Correct 162 ms 43020 KB Output is correct
11 Correct 169 ms 42112 KB Output is correct
12 Correct 170 ms 44348 KB Output is correct
13 Correct 131 ms 43184 KB Output is correct
14 Correct 143 ms 35648 KB Output is correct
15 Correct 354 ms 47488 KB Output is correct
16 Correct 368 ms 45064 KB Output is correct
17 Correct 370 ms 50088 KB Output is correct
18 Correct 334 ms 46104 KB Output is correct
19 Correct 106 ms 18432 KB Output is correct
20 Correct 345 ms 47932 KB Output is correct
21 Correct 344 ms 46240 KB Output is correct
22 Correct 407 ms 49700 KB Output is correct
23 Correct 349 ms 47112 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 187 ms 40168 KB Output is correct
4 Correct 188 ms 41504 KB Output is correct
5 Correct 190 ms 41024 KB Output is correct
6 Correct 180 ms 41244 KB Output is correct
7 Correct 191 ms 41364 KB Output is correct
8 Correct 182 ms 40028 KB Output is correct
9 Correct 190 ms 41088 KB Output is correct
10 Correct 184 ms 39832 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7492 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7628 KB Output is correct
7 Correct 6 ms 7724 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7628 KB Output is correct
11 Correct 4 ms 7636 KB Output is correct
12 Correct 5 ms 7628 KB Output is correct
13 Correct 5 ms 7620 KB Output is correct
14 Correct 5 ms 7636 KB Output is correct
15 Correct 5 ms 7636 KB Output is correct
16 Correct 5 ms 7728 KB Output is correct
17 Correct 5 ms 7636 KB Output is correct
18 Correct 5 ms 7632 KB Output is correct
19 Correct 5 ms 7508 KB Output is correct
20 Correct 6 ms 7632 KB Output is correct
21 Correct 5 ms 7636 KB Output is correct
22 Correct 5 ms 7508 KB Output is correct
23 Correct 5 ms 7632 KB Output is correct
24 Correct 5 ms 7764 KB Output is correct
25 Correct 5 ms 7636 KB Output is correct
26 Correct 6 ms 7764 KB Output is correct
27 Correct 6 ms 7636 KB Output is correct
28 Correct 7 ms 7636 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7492 KB Output is correct
6 Correct 5 ms 7636 KB Output is correct
7 Correct 5 ms 7628 KB Output is correct
8 Correct 6 ms 7724 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 132 ms 36024 KB Output is correct
11 Correct 162 ms 43020 KB Output is correct
12 Correct 169 ms 42112 KB Output is correct
13 Correct 170 ms 44348 KB Output is correct
14 Correct 131 ms 43184 KB Output is correct
15 Correct 5 ms 7628 KB Output is correct
16 Correct 4 ms 7636 KB Output is correct
17 Correct 5 ms 7628 KB Output is correct
18 Correct 5 ms 7620 KB Output is correct
19 Correct 5 ms 7636 KB Output is correct
20 Correct 5 ms 7636 KB Output is correct
21 Correct 5 ms 7728 KB Output is correct
22 Correct 5 ms 7636 KB Output is correct
23 Correct 5 ms 7632 KB Output is correct
24 Correct 5 ms 7508 KB Output is correct
25 Correct 6 ms 7632 KB Output is correct
26 Correct 5 ms 7636 KB Output is correct
27 Correct 5 ms 7508 KB Output is correct
28 Correct 5 ms 7632 KB Output is correct
29 Correct 5 ms 7764 KB Output is correct
30 Correct 5 ms 7636 KB Output is correct
31 Correct 6 ms 7764 KB Output is correct
32 Correct 6 ms 7636 KB Output is correct
33 Correct 7 ms 7636 KB Output is correct
34 Correct 16 ms 11668 KB Output is correct
35 Correct 161 ms 43696 KB Output is correct
36 Correct 163 ms 41572 KB Output is correct
37 Correct 171 ms 39564 KB Output is correct
38 Correct 171 ms 38676 KB Output is correct
39 Correct 140 ms 37952 KB Output is correct
40 Correct 137 ms 35508 KB Output is correct
41 Correct 164 ms 42688 KB Output is correct
42 Correct 174 ms 43452 KB Output is correct
43 Correct 141 ms 41516 KB Output is correct
44 Correct 148 ms 38972 KB Output is correct
45 Correct 132 ms 34776 KB Output is correct
46 Correct 161 ms 40664 KB Output is correct
47 Correct 164 ms 37824 KB Output is correct
48 Correct 146 ms 36920 KB Output is correct
49 Correct 63 ms 16980 KB Output is correct
50 Correct 50 ms 15812 KB Output is correct
51 Correct 101 ms 30216 KB Output is correct
52 Correct 184 ms 44044 KB Output is correct
53 Correct 170 ms 42836 KB Output is correct
54 Correct 206 ms 47832 KB Output is correct
55 Correct 136 ms 42500 KB Output is correct
56 Correct 169 ms 41588 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7492 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7628 KB Output is correct
7 Correct 6 ms 7724 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 132 ms 36024 KB Output is correct
10 Correct 162 ms 43020 KB Output is correct
11 Correct 169 ms 42112 KB Output is correct
12 Correct 170 ms 44348 KB Output is correct
13 Correct 131 ms 43184 KB Output is correct
14 Correct 143 ms 35648 KB Output is correct
15 Correct 354 ms 47488 KB Output is correct
16 Correct 368 ms 45064 KB Output is correct
17 Correct 370 ms 50088 KB Output is correct
18 Correct 334 ms 46104 KB Output is correct
19 Correct 187 ms 40168 KB Output is correct
20 Correct 188 ms 41504 KB Output is correct
21 Correct 190 ms 41024 KB Output is correct
22 Correct 180 ms 41244 KB Output is correct
23 Correct 191 ms 41364 KB Output is correct
24 Correct 182 ms 40028 KB Output is correct
25 Correct 190 ms 41088 KB Output is correct
26 Correct 184 ms 39832 KB Output is correct
27 Correct 5 ms 7628 KB Output is correct
28 Correct 4 ms 7636 KB Output is correct
29 Correct 5 ms 7628 KB Output is correct
30 Correct 5 ms 7620 KB Output is correct
31 Correct 5 ms 7636 KB Output is correct
32 Correct 5 ms 7636 KB Output is correct
33 Correct 5 ms 7728 KB Output is correct
34 Correct 5 ms 7636 KB Output is correct
35 Correct 5 ms 7632 KB Output is correct
36 Correct 16 ms 11668 KB Output is correct
37 Correct 161 ms 43696 KB Output is correct
38 Correct 163 ms 41572 KB Output is correct
39 Correct 171 ms 39564 KB Output is correct
40 Correct 171 ms 38676 KB Output is correct
41 Correct 140 ms 37952 KB Output is correct
42 Correct 137 ms 35508 KB Output is correct
43 Correct 164 ms 42688 KB Output is correct
44 Correct 174 ms 43452 KB Output is correct
45 Correct 141 ms 41516 KB Output is correct
46 Correct 148 ms 38972 KB Output is correct
47 Correct 24 ms 11832 KB Output is correct
48 Correct 375 ms 47136 KB Output is correct
49 Correct 362 ms 45672 KB Output is correct
50 Correct 349 ms 44584 KB Output is correct
51 Correct 322 ms 43760 KB Output is correct
52 Correct 278 ms 41584 KB Output is correct
53 Correct 193 ms 34244 KB Output is correct
54 Correct 357 ms 47488 KB Output is correct
55 Correct 360 ms 47840 KB Output is correct
56 Correct 338 ms 47012 KB Output is correct
57 Correct 273 ms 44348 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7492 KB Output is correct
6 Correct 5 ms 7636 KB Output is correct
7 Correct 5 ms 7628 KB Output is correct
8 Correct 6 ms 7724 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 132 ms 36024 KB Output is correct
11 Correct 162 ms 43020 KB Output is correct
12 Correct 169 ms 42112 KB Output is correct
13 Correct 170 ms 44348 KB Output is correct
14 Correct 131 ms 43184 KB Output is correct
15 Correct 143 ms 35648 KB Output is correct
16 Correct 354 ms 47488 KB Output is correct
17 Correct 368 ms 45064 KB Output is correct
18 Correct 370 ms 50088 KB Output is correct
19 Correct 334 ms 46104 KB Output is correct
20 Correct 187 ms 40168 KB Output is correct
21 Correct 188 ms 41504 KB Output is correct
22 Correct 190 ms 41024 KB Output is correct
23 Correct 180 ms 41244 KB Output is correct
24 Correct 191 ms 41364 KB Output is correct
25 Correct 182 ms 40028 KB Output is correct
26 Correct 190 ms 41088 KB Output is correct
27 Correct 184 ms 39832 KB Output is correct
28 Correct 5 ms 7628 KB Output is correct
29 Correct 4 ms 7636 KB Output is correct
30 Correct 5 ms 7628 KB Output is correct
31 Correct 5 ms 7620 KB Output is correct
32 Correct 5 ms 7636 KB Output is correct
33 Correct 5 ms 7636 KB Output is correct
34 Correct 5 ms 7728 KB Output is correct
35 Correct 5 ms 7636 KB Output is correct
36 Correct 5 ms 7632 KB Output is correct
37 Correct 16 ms 11668 KB Output is correct
38 Correct 161 ms 43696 KB Output is correct
39 Correct 163 ms 41572 KB Output is correct
40 Correct 171 ms 39564 KB Output is correct
41 Correct 171 ms 38676 KB Output is correct
42 Correct 140 ms 37952 KB Output is correct
43 Correct 137 ms 35508 KB Output is correct
44 Correct 164 ms 42688 KB Output is correct
45 Correct 174 ms 43452 KB Output is correct
46 Correct 141 ms 41516 KB Output is correct
47 Correct 148 ms 38972 KB Output is correct
48 Correct 24 ms 11832 KB Output is correct
49 Correct 375 ms 47136 KB Output is correct
50 Correct 362 ms 45672 KB Output is correct
51 Correct 349 ms 44584 KB Output is correct
52 Correct 322 ms 43760 KB Output is correct
53 Correct 278 ms 41584 KB Output is correct
54 Correct 193 ms 34244 KB Output is correct
55 Correct 357 ms 47488 KB Output is correct
56 Correct 360 ms 47840 KB Output is correct
57 Correct 338 ms 47012 KB Output is correct
58 Correct 273 ms 44348 KB Output is correct
59 Correct 106 ms 18432 KB Output is correct
60 Correct 345 ms 47932 KB Output is correct
61 Correct 344 ms 46240 KB Output is correct
62 Correct 407 ms 49700 KB Output is correct
63 Correct 349 ms 47112 KB Output is correct
64 Correct 5 ms 7508 KB Output is correct
65 Correct 6 ms 7632 KB Output is correct
66 Correct 5 ms 7636 KB Output is correct
67 Correct 5 ms 7508 KB Output is correct
68 Correct 5 ms 7632 KB Output is correct
69 Correct 5 ms 7764 KB Output is correct
70 Correct 5 ms 7636 KB Output is correct
71 Correct 6 ms 7764 KB Output is correct
72 Correct 6 ms 7636 KB Output is correct
73 Correct 7 ms 7636 KB Output is correct
74 Correct 132 ms 34776 KB Output is correct
75 Correct 161 ms 40664 KB Output is correct
76 Correct 164 ms 37824 KB Output is correct
77 Correct 146 ms 36920 KB Output is correct
78 Correct 63 ms 16980 KB Output is correct
79 Correct 50 ms 15812 KB Output is correct
80 Correct 101 ms 30216 KB Output is correct
81 Correct 184 ms 44044 KB Output is correct
82 Correct 170 ms 42836 KB Output is correct
83 Correct 206 ms 47832 KB Output is correct
84 Correct 136 ms 42500 KB Output is correct
85 Correct 169 ms 41588 KB Output is correct
86 Correct 62 ms 18860 KB Output is correct
87 Correct 349 ms 44956 KB Output is correct
88 Correct 352 ms 45224 KB Output is correct
89 Correct 236 ms 40088 KB Output is correct
90 Correct 138 ms 20796 KB Output is correct
91 Correct 155 ms 22704 KB Output is correct
92 Correct 211 ms 35116 KB Output is correct
93 Correct 390 ms 48668 KB Output is correct
94 Correct 312 ms 47244 KB Output is correct
95 Correct 394 ms 51764 KB Output is correct
96 Correct 334 ms 45336 KB Output is correct
97 Correct 269 ms 44540 KB Output is correct