oj.uz

Submission #1109723

# Submission time Handle Problem Language Result Execution time Memory
1109723 2024-11-07T11:34:25 Z Mike_Vu Swapping Cities (APIO20_swap) C++14
100 / 100
 256 ms 71184 KB 
#ifndef mikevui
//    #include "task.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct edge{
    int u, v, w;
    edge(int _u, int _v, int _w) {
        u = _u;
        v = _v;
        w = _w;
    }
};

const int maxn = 3e5+5, lg = 19;
int n, m, trsz;
vector<edge> edges;
bool can[maxn];
int ans[maxn];
vector<int> adj[maxn];
int par[maxn][lg+1], h[maxn];
bool hadcan[maxn][lg+1];

namespace dsu{
    vector<int> dsu, deg, sumdeg;
    void init() {
        trsz = n;
        memset(can, 0, sizeof(can));
        dsu.assign(trsz+1, 0);
        deg.assign(trsz+1, 0);
        sumdeg.assign(trsz+1, 1);
        for (int i = 1; i <= n; i++) {
            dsu[i] = i;
        }
    }
    int f(int u) {
        if (u == dsu[u]) return u;
        return dsu[u] = f(dsu[u]);
    }
    void addedge(int u, int v) {
        int ru = f(u), rv = f(v);
        ++trsz;
        dsu.pb(trsz);
        dsu[ru] = dsu[rv] = trsz;
        adj[trsz].pb(ru);
        if (ru != rv) adj[trsz].pb(rv);
        ++deg[u];
        ++deg[v];
        //check cycle
        sumdeg.pb(sumdeg[ru]);
        if (ru != rv) sumdeg[trsz] += sumdeg[rv];
        if (deg[u] == 2)--sumdeg[trsz];
        if (deg[v] == 2)--sumdeg[trsz];
//        cout << u << ' ' << v << ' ' << trsz << "\n" << deg[u] << ' ' << deg[v] << ' ' << sumdeg[ru] << ' ' << sumdeg[rv] << ' ' << sumdeg[trsz] << "\n";
        can[trsz] = (max(deg[u], deg[v])>2 || sumdeg[trsz] == 0);
        can[trsz] |= can[ru] | can[rv];
    }
}

void dfs(int u) {
    //setup binlift
    for (int j = 1; j <= lg; j++) {
        par[u][j] = par[par[u][j-1]][j-1];
        hadcan[u][j] = hadcan[u][j-1]|hadcan[par[u][j-1]][j-1];
    }
    //dfs
    for (int v : adj[u]) {
        par[v][0] = u;
        hadcan[v][0] = can[u];
        h[v] = h[u]+1;
        dfs(v);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    if (h[u] > h[v]) {
        int k = h[u]-h[v];
        for (int j = lg; j >= 0; j--) {
            if (BITj(k, j)) {
                u = par[u][j];
            }
        }
    }
    if (u == v) return u;
    for (int j = lg; j >= 0; j--) {
        while (h[u] > MASK(j) && par[u][j] != par[v][j]) {
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}

int findnearest(int u){
    for (int j = lg; j >= 0; j--) {
        while (h[u] > MASK(j) && !hadcan[u][j]) {
            u = par[u][j];
        }
    }
    return par[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    //transform to normal use
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        int u = U[i]+1, v = V[i]+1, w = W[i];
        edges.pb(edge(u, v, w));
    }
    //build dsu tree
    sort(edges.begin(), edges.end(), [&](edge a, edge b){return a.w<b.w;});
    dsu::init();
    for (int i= 0; i < m; i++) {
        dsu::addedge(edges[i].u, edges[i].v);
        ans[trsz] = edges[i].w;
    }
    //build binlift
    memset(par, 0, sizeof(par));
    memset(hadcan, 0, sizeof(hadcan));
    h[trsz] = 1;
    dfs(trsz);
//    for (int i = trsz; i; i--) {
//        cout << i << ' ' << h[i] << ' ' << can[i] << ' ' << ans[i] << "\n";
//    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int x = X+1, y = Y+1;
    //lca
    int l = lca(x, y);
    //check if lca can
    if (can[l]) {
        return ans[l];
    }
    //if not -> find nearest can
    l = findnearest(l);
    //case cannot
    if (!can[l]) return -1;
    return ans[l];
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int N, M;
    cin >> N >> M;
    vector<int> U, V, W;
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        U.pb(u);
        V.pb(v);
        W.pb(w);
    }
    init(N,M,U,V,W);
    int Q;
    cin >> Q;
    while (Q--) {
        int X, Y;
        cin >> X >> Y;
        cout << getMinimumFuelCapacity(X,Y) << "\n";
    }
}
#endif // mikevui
/*
5 4
0 1 6
0 2 4
0 3 4
1 4 6
1
4 0

6

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
0 2
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 6 ms 38392 KB Output is correct
3 Correct 6 ms 38224 KB Output is correct
4 Correct 6 ms 38224 KB Output is correct
5 Correct 7 ms 38224 KB Output is correct
6 Correct 7 ms 38224 KB Output is correct
7 Correct 7 ms 38408 KB Output is correct
8 Correct 6 ms 38224 KB Output is correct
9 Correct 76 ms 45292 KB Output is correct
10 Correct 82 ms 46756 KB Output is correct
11 Correct 79 ms 46824 KB Output is correct
12 Correct 89 ms 47292 KB Output is correct
13 Correct 90 ms 51132 KB Output is correct
14 Correct 85 ms 45492 KB Output is correct
15 Correct 141 ms 48712 KB Output is correct
16 Correct 140 ms 48492 KB Output is correct
17 Correct 142 ms 48936 KB Output is correct
18 Correct 207 ms 52780 KB Output is correct
19 Correct 62 ms 43024 KB Output is correct
20 Correct 149 ms 49980 KB Output is correct
21 Correct 160 ms 49784 KB Output is correct
22 Correct 195 ms 50480 KB Output is correct
23 Correct 212 ms 54308 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 6 ms 38392 KB Output is correct
3 Correct 177 ms 57068 KB Output is correct
4 Correct 195 ms 57868 KB Output is correct
5 Correct 167 ms 57492 KB Output is correct
6 Correct 166 ms 57636 KB Output is correct
7 Correct 204 ms 57700 KB Output is correct
8 Correct 182 ms 56940 KB Output is correct
9 Correct 174 ms 57460 KB Output is correct
10 Correct 195 ms 56904 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 6 ms 38392 KB Output is correct
3 Correct 6 ms 38224 KB Output is correct
4 Correct 6 ms 38224 KB Output is correct
5 Correct 7 ms 38224 KB Output is correct
6 Correct 7 ms 38224 KB Output is correct
7 Correct 7 ms 38408 KB Output is correct
8 Correct 6 ms 38224 KB Output is correct
9 Correct 7 ms 38392 KB Output is correct
10 Correct 7 ms 38224 KB Output is correct
11 Correct 7 ms 38228 KB Output is correct
12 Correct 8 ms 38236 KB Output is correct
13 Correct 8 ms 38224 KB Output is correct
14 Correct 7 ms 38224 KB Output is correct
15 Correct 8 ms 38428 KB Output is correct
16 Correct 8 ms 38224 KB Output is correct
17 Correct 7 ms 38224 KB Output is correct
18 Correct 7 ms 38224 KB Output is correct
19 Correct 8 ms 38224 KB Output is correct
20 Correct 7 ms 38224 KB Output is correct
21 Correct 7 ms 38652 KB Output is correct
22 Correct 8 ms 38480 KB Output is correct
23 Correct 7 ms 38224 KB Output is correct
24 Correct 8 ms 38480 KB Output is correct
25 Correct 9 ms 38480 KB Output is correct
26 Correct 9 ms 38488 KB Output is correct
27 Correct 7 ms 38480 KB Output is correct
28 Correct 7 ms 38480 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38392 KB Output is correct
2 Correct 6 ms 38224 KB Output is correct
3 Correct 6 ms 38392 KB Output is correct
4 Correct 6 ms 38224 KB Output is correct
5 Correct 6 ms 38224 KB Output is correct
6 Correct 7 ms 38224 KB Output is correct
7 Correct 7 ms 38224 KB Output is correct
8 Correct 7 ms 38408 KB Output is correct
9 Correct 6 ms 38224 KB Output is correct
10 Correct 76 ms 45292 KB Output is correct
11 Correct 82 ms 46756 KB Output is correct
12 Correct 79 ms 46824 KB Output is correct
13 Correct 89 ms 47292 KB Output is correct
14 Correct 90 ms 51132 KB Output is correct
15 Correct 7 ms 38224 KB Output is correct
16 Correct 7 ms 38228 KB Output is correct
17 Correct 8 ms 38236 KB Output is correct
18 Correct 8 ms 38224 KB Output is correct
19 Correct 7 ms 38224 KB Output is correct
20 Correct 8 ms 38428 KB Output is correct
21 Correct 8 ms 38224 KB Output is correct
22 Correct 7 ms 38224 KB Output is correct
23 Correct 7 ms 38224 KB Output is correct
24 Correct 8 ms 38224 KB Output is correct
25 Correct 7 ms 38224 KB Output is correct
26 Correct 7 ms 38652 KB Output is correct
27 Correct 8 ms 38480 KB Output is correct
28 Correct 7 ms 38224 KB Output is correct
29 Correct 8 ms 38480 KB Output is correct
30 Correct 9 ms 38480 KB Output is correct
31 Correct 9 ms 38488 KB Output is correct
32 Correct 7 ms 38480 KB Output is correct
33 Correct 7 ms 38480 KB Output is correct
34 Correct 20 ms 39720 KB Output is correct
35 Correct 104 ms 49092 KB Output is correct
36 Correct 95 ms 48916 KB Output is correct
37 Correct 108 ms 49084 KB Output is correct
38 Correct 108 ms 48904 KB Output is correct
39 Correct 96 ms 48828 KB Output is correct
40 Correct 95 ms 48036 KB Output is correct
41 Correct 98 ms 49380 KB Output is correct
42 Correct 101 ms 48924 KB Output is correct
43 Correct 106 ms 54216 KB Output is correct
44 Correct 105 ms 49340 KB Output is correct
45 Correct 154 ms 61364 KB Output is correct
46 Correct 98 ms 49052 KB Output is correct
47 Correct 104 ms 49280 KB Output is correct
48 Correct 122 ms 54296 KB Output is correct
49 Correct 105 ms 66380 KB Output is correct
50 Correct 84 ms 59836 KB Output is correct
51 Correct 116 ms 58244 KB Output is correct
52 Correct 142 ms 60344 KB Output is correct
53 Correct 160 ms 61628 KB Output is correct
54 Correct 168 ms 66740 KB Output is correct
55 Correct 91 ms 53624 KB Output is correct
56 Correct 145 ms 64400 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38224 KB Output is correct
2 Correct 6 ms 38392 KB Output is correct
3 Correct 6 ms 38224 KB Output is correct
4 Correct 6 ms 38224 KB Output is correct
5 Correct 7 ms 38224 KB Output is correct
6 Correct 7 ms 38224 KB Output is correct
7 Correct 7 ms 38408 KB Output is correct
8 Correct 6 ms 38224 KB Output is correct
9 Correct 76 ms 45292 KB Output is correct
10 Correct 82 ms 46756 KB Output is correct
11 Correct 79 ms 46824 KB Output is correct
12 Correct 89 ms 47292 KB Output is correct
13 Correct 90 ms 51132 KB Output is correct
14 Correct 85 ms 45492 KB Output is correct
15 Correct 141 ms 48712 KB Output is correct
16 Correct 140 ms 48492 KB Output is correct
17 Correct 142 ms 48936 KB Output is correct
18 Correct 207 ms 52780 KB Output is correct
19 Correct 177 ms 57068 KB Output is correct
20 Correct 195 ms 57868 KB Output is correct
21 Correct 167 ms 57492 KB Output is correct
22 Correct 166 ms 57636 KB Output is correct
23 Correct 204 ms 57700 KB Output is correct
24 Correct 182 ms 56940 KB Output is correct
25 Correct 174 ms 57460 KB Output is correct
26 Correct 195 ms 56904 KB Output is correct
27 Correct 7 ms 38224 KB Output is correct
28 Correct 7 ms 38228 KB Output is correct
29 Correct 8 ms 38236 KB Output is correct
30 Correct 8 ms 38224 KB Output is correct
31 Correct 7 ms 38224 KB Output is correct
32 Correct 8 ms 38428 KB Output is correct
33 Correct 8 ms 38224 KB Output is correct
34 Correct 7 ms 38224 KB Output is correct
35 Correct 7 ms 38224 KB Output is correct
36 Correct 20 ms 39720 KB Output is correct
37 Correct 104 ms 49092 KB Output is correct
38 Correct 95 ms 48916 KB Output is correct
39 Correct 108 ms 49084 KB Output is correct
40 Correct 108 ms 48904 KB Output is correct
41 Correct 96 ms 48828 KB Output is correct
42 Correct 95 ms 48036 KB Output is correct
43 Correct 98 ms 49380 KB Output is correct
44 Correct 101 ms 48924 KB Output is correct
45 Correct 106 ms 54216 KB Output is correct
46 Correct 105 ms 49340 KB Output is correct
47 Correct 25 ms 40208 KB Output is correct
48 Correct 152 ms 53896 KB Output is correct
49 Correct 147 ms 53932 KB Output is correct
50 Correct 146 ms 53884 KB Output is correct
51 Correct 177 ms 53808 KB Output is correct
52 Correct 167 ms 53356 KB Output is correct
53 Correct 139 ms 51376 KB Output is correct
54 Correct 186 ms 54824 KB Output is correct
55 Correct 162 ms 53796 KB Output is correct
56 Correct 202 ms 57996 KB Output is correct
57 Correct 180 ms 54820 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38392 KB Output is correct
2 Correct 6 ms 38224 KB Output is correct
3 Correct 6 ms 38392 KB Output is correct
4 Correct 6 ms 38224 KB Output is correct
5 Correct 6 ms 38224 KB Output is correct
6 Correct 7 ms 38224 KB Output is correct
7 Correct 7 ms 38224 KB Output is correct
8 Correct 7 ms 38408 KB Output is correct
9 Correct 6 ms 38224 KB Output is correct
10 Correct 76 ms 45292 KB Output is correct
11 Correct 82 ms 46756 KB Output is correct
12 Correct 79 ms 46824 KB Output is correct
13 Correct 89 ms 47292 KB Output is correct
14 Correct 90 ms 51132 KB Output is correct
15 Correct 85 ms 45492 KB Output is correct
16 Correct 141 ms 48712 KB Output is correct
17 Correct 140 ms 48492 KB Output is correct
18 Correct 142 ms 48936 KB Output is correct
19 Correct 207 ms 52780 KB Output is correct
20 Correct 177 ms 57068 KB Output is correct
21 Correct 195 ms 57868 KB Output is correct
22 Correct 167 ms 57492 KB Output is correct
23 Correct 166 ms 57636 KB Output is correct
24 Correct 204 ms 57700 KB Output is correct
25 Correct 182 ms 56940 KB Output is correct
26 Correct 174 ms 57460 KB Output is correct
27 Correct 195 ms 56904 KB Output is correct
28 Correct 7 ms 38224 KB Output is correct
29 Correct 7 ms 38228 KB Output is correct
30 Correct 8 ms 38236 KB Output is correct
31 Correct 8 ms 38224 KB Output is correct
32 Correct 7 ms 38224 KB Output is correct
33 Correct 8 ms 38428 KB Output is correct
34 Correct 8 ms 38224 KB Output is correct
35 Correct 7 ms 38224 KB Output is correct
36 Correct 7 ms 38224 KB Output is correct
37 Correct 20 ms 39720 KB Output is correct
38 Correct 104 ms 49092 KB Output is correct
39 Correct 95 ms 48916 KB Output is correct
40 Correct 108 ms 49084 KB Output is correct
41 Correct 108 ms 48904 KB Output is correct
42 Correct 96 ms 48828 KB Output is correct
43 Correct 95 ms 48036 KB Output is correct
44 Correct 98 ms 49380 KB Output is correct
45 Correct 101 ms 48924 KB Output is correct
46 Correct 106 ms 54216 KB Output is correct
47 Correct 105 ms 49340 KB Output is correct
48 Correct 25 ms 40208 KB Output is correct
49 Correct 152 ms 53896 KB Output is correct
50 Correct 147 ms 53932 KB Output is correct
51 Correct 146 ms 53884 KB Output is correct
52 Correct 177 ms 53808 KB Output is correct
53 Correct 167 ms 53356 KB Output is correct
54 Correct 139 ms 51376 KB Output is correct
55 Correct 186 ms 54824 KB Output is correct
56 Correct 162 ms 53796 KB Output is correct
57 Correct 202 ms 57996 KB Output is correct
58 Correct 180 ms 54820 KB Output is correct
59 Correct 62 ms 43024 KB Output is correct
60 Correct 149 ms 49980 KB Output is correct
61 Correct 160 ms 49784 KB Output is correct
62 Correct 195 ms 50480 KB Output is correct
63 Correct 212 ms 54308 KB Output is correct
64 Correct 8 ms 38224 KB Output is correct
65 Correct 7 ms 38224 KB Output is correct
66 Correct 7 ms 38652 KB Output is correct
67 Correct 8 ms 38480 KB Output is correct
68 Correct 7 ms 38224 KB Output is correct
69 Correct 8 ms 38480 KB Output is correct
70 Correct 9 ms 38480 KB Output is correct
71 Correct 9 ms 38488 KB Output is correct
72 Correct 7 ms 38480 KB Output is correct
73 Correct 7 ms 38480 KB Output is correct
74 Correct 154 ms 61364 KB Output is correct
75 Correct 98 ms 49052 KB Output is correct
76 Correct 104 ms 49280 KB Output is correct
77 Correct 122 ms 54296 KB Output is correct
78 Correct 105 ms 66380 KB Output is correct
79 Correct 84 ms 59836 KB Output is correct
80 Correct 116 ms 58244 KB Output is correct
81 Correct 142 ms 60344 KB Output is correct
82 Correct 160 ms 61628 KB Output is correct
83 Correct 168 ms 66740 KB Output is correct
84 Correct 91 ms 53624 KB Output is correct
85 Correct 145 ms 64400 KB Output is correct
86 Correct 69 ms 46796 KB Output is correct
87 Correct 182 ms 53996 KB Output is correct
88 Correct 169 ms 54016 KB Output is correct
89 Correct 219 ms 57564 KB Output is correct
90 Correct 165 ms 71184 KB Output is correct
91 Correct 192 ms 68572 KB Output is correct
92 Correct 222 ms 62384 KB Output is correct
93 Correct 224 ms 64624 KB Output is correct
94 Correct 252 ms 66464 KB Output is correct
95 Correct 256 ms 70584 KB Output is correct
96 Correct 198 ms 58372 KB Output is correct
97 Correct 229 ms 63612 KB Output is correct