oj.uz

Submission #558033

# Submission time Handle Problem Language Result Execution time Memory
558033 2022-05-06T14:09:43 Z InternetPerson10 Swapping Cities (APIO20_swap) C++17
100 / 100
 477 ms 50420 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

int BIG = 1e9 + 7; // 
int second[100001];
int third[100001];
int depth[100001];
int parent[100001];
int parWeight[100001];
int liftWt[100001][20]; // The maximum of weights when going above
int liftVal[100001][20]; // The vertex that is 2^i above
int liftMin[100001][20]; // The minimum of the thirds up to 2^i above

vector<vector<pair<int, int>>> adj;

void dfs(int n, int par = -1) {
    for(auto p : adj[n]) {
        int ch, w;
        tie(ch, w) = p;
        if(ch == par) continue;
        parWeight[ch] = w;
        parent[ch] = n;
        depth[ch] = depth[n] + 1;
        dfs(ch, n);
    }
}

struct dsu {
    vector<int> par, siz, lin, linen;
    void init(int n) {
        par.resize(n);
        siz.resize(n, 1);
        lin.resize(n, BIG);
        linen.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(par[x] == x) return x;
        int g = get(par[x]);
        if(lin[x] != BIG) return par[x] = g;
        if(lin[par[x]] != BIG) {
            lin[x] = lin[par[x]];
            linen[x] = 0;
        }
        return par[x] = g;
    }
    bool unite(int x, int y, int w) {
        int gx = get(x), gy = get(y);
        if(gx == gy) {
            if(lin[gx] == BIG) {
                lin[gx] = w;
                linen[gx] = 0;
            }
            return false;
        }
        // Connecting a line and a line, becomes a line
        if(lin[gx] == BIG && lin[gy] == BIG && linen[x] && linen[y]) {
            if(siz[gx] != 1) linen[x] = 0;
            if(siz[gy] != 1) linen[y] = 0;
        }
        // Connecting a line and a line, doesn't become a line
        else {
            lin[gx] = min(lin[gx], w);
            lin[gy] = min(lin[gy], w);
            linen[x] = linen[y] = 0;
        }
        x = gx; y = gy;
        if(siz[x] > siz[y]) swap(x, y);
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

dsu uf;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vector<pair<int, pair<int, int>>> edges(M);
    for(int i = 0; i < N; i++) {
        depth[i] = 0;
        second[i] = BIG;
        third[i] = -1;
        parent[i] = 0;
    }
    adj.resize(N);
    for(int i = 0; i < M; i++) {
        edges[i] = {W[i], {U[i], V[i]}};
    }
    sort(edges.begin(), edges.end());
    uf.init(N);
    for(auto [w, p] : edges) {
        int u, v;
        tie(u, v) = p;
        if(third[u] < 0) {
            third[u]--;
            if(third[u] == -3) second[u] = w;
            if(third[u] == -4) third[u] = w;
        }
        if(third[v] < 0) {
            third[v]--;
            if(third[v] == -3) second[v] = w;
            if(third[v] == -4) third[v] = w;
        }
        if(uf.unite(u, v, w)) {
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }
    for(int i = 0; i < N; i++) {
        uf.get(i);
        // cout << i << ' ' << uf.lin[i] << endl;
        if(third[i] < 0) third[i] = BIG;
    }
    dfs(0);
    for(int i = 0; i < 20; i++) {
        liftWt[0][i] = liftVal[0][i] = 0;
        liftMin[0][i] = third[0];
    }
    for(int x = 1; x < N; x++) {
        liftWt[x][0] = parWeight[x];
        liftVal[x][0] = parent[x];
        liftMin[x][0] = min(third[x], third[parent[x]]);
    }
    for(int i = 1; i < 20; i++) {
        for(int x = 1; x < N; x++) {
            int xUp = liftVal[x][i-1];
            liftWt[x][i] = max(liftWt[x][i-1], liftWt[xUp][i-1]);
            liftVal[x][i] = liftVal[xUp][i-1];
            liftMin[x][i] = min(liftMin[x][i-1], liftMin[xUp][i-1]);
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    int weightMax = 0, thirdMin = BIG;
    int secondx = uf.lin[x], secondy = uf.lin[y];
    if(depth[x] > depth[y]) swap(x, y);
    if(depth[x] < depth[y]) {
        int g = depth[y] - depth[x];
        for(int i = 0; i < 20; i++) {
            if(g & (1 << i)) {
                weightMax = max(weightMax, liftWt[y][i]);
                thirdMin = min(thirdMin, liftMin[y][i]);
                y = liftVal[y][i];
            }
        }
    }
    for(int i = 19; i >= 0; i--) {
        if(liftVal[x][i] != liftVal[y][i]) {
            weightMax = max(weightMax, liftWt[x][i]);
            thirdMin = min(thirdMin, liftMin[x][i]);
            x = liftVal[x][i];
            weightMax = max(weightMax, liftWt[y][i]);
            thirdMin = min(thirdMin, liftMin[y][i]);
            y = liftVal[y][i];
        }
        if(i == 0 && x != y) {
            weightMax = max(weightMax, liftWt[x][i]);
            thirdMin = min(thirdMin, liftMin[x][i]);
            x = liftVal[x][i];
            weightMax = max(weightMax, liftWt[y][i]);
            thirdMin = min(thirdMin, liftMin[y][i]);
            y = liftVal[y][i];
        }
    }
    int ans = max(weightMax, min(thirdMin, min(secondx, secondy)));
    if(ans == BIG) return -1;
    return ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 113 ms 31740 KB Output is correct
10 Correct 158 ms 39836 KB Output is correct
11 Correct 154 ms 38716 KB Output is correct
12 Correct 168 ms 41156 KB Output is correct
13 Correct 149 ms 42604 KB Output is correct
14 Correct 135 ms 31180 KB Output is correct
15 Correct 390 ms 41408 KB Output is correct
16 Correct 458 ms 39024 KB Output is correct
17 Correct 395 ms 44156 KB Output is correct
18 Correct 429 ms 43040 KB Output is correct
19 Correct 85 ms 10384 KB Output is correct
20 Correct 449 ms 41168 KB Output is correct
21 Correct 422 ms 39236 KB Output is correct
22 Correct 436 ms 42684 KB Output is correct
23 Correct 415 ms 43048 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 185 ms 37192 KB Output is correct
4 Correct 182 ms 38760 KB Output is correct
5 Correct 198 ms 37876 KB Output is correct
6 Correct 177 ms 38672 KB Output is correct
7 Correct 188 ms 38320 KB Output is correct
8 Correct 194 ms 37028 KB Output is correct
9 Correct 176 ms 38032 KB Output is correct
10 Correct 200 ms 36600 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 1 ms 704 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 1 ms 572 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 2 ms 704 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 2 ms 724 KB Output is correct
28 Correct 2 ms 724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 704 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 113 ms 31740 KB Output is correct
11 Correct 158 ms 39836 KB Output is correct
12 Correct 154 ms 38716 KB Output is correct
13 Correct 168 ms 41156 KB Output is correct
14 Correct 149 ms 42604 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 724 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 1 ms 704 KB Output is correct
23 Correct 1 ms 724 KB Output is correct
24 Correct 1 ms 572 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 2 ms 704 KB Output is correct
30 Correct 2 ms 852 KB Output is correct
31 Correct 2 ms 724 KB Output is correct
32 Correct 2 ms 724 KB Output is correct
33 Correct 2 ms 724 KB Output is correct
34 Correct 14 ms 5588 KB Output is correct
35 Correct 149 ms 42472 KB Output is correct
36 Correct 150 ms 40380 KB Output is correct
37 Correct 158 ms 38912 KB Output is correct
38 Correct 135 ms 37964 KB Output is correct
39 Correct 134 ms 37468 KB Output is correct
40 Correct 118 ms 34628 KB Output is correct
41 Correct 155 ms 41264 KB Output is correct
42 Correct 156 ms 41832 KB Output is correct
43 Correct 140 ms 42812 KB Output is correct
44 Correct 130 ms 39000 KB Output is correct
45 Correct 142 ms 34552 KB Output is correct
46 Correct 155 ms 39588 KB Output is correct
47 Correct 128 ms 38076 KB Output is correct
48 Correct 124 ms 38060 KB Output is correct
49 Correct 60 ms 9008 KB Output is correct
50 Correct 50 ms 9292 KB Output is correct
51 Correct 105 ms 28576 KB Output is correct
52 Correct 195 ms 43272 KB Output is correct
53 Correct 164 ms 43852 KB Output is correct
54 Correct 194 ms 46640 KB Output is correct
55 Correct 176 ms 43940 KB Output is correct
56 Correct 177 ms 42956 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 113 ms 31740 KB Output is correct
10 Correct 158 ms 39836 KB Output is correct
11 Correct 154 ms 38716 KB Output is correct
12 Correct 168 ms 41156 KB Output is correct
13 Correct 149 ms 42604 KB Output is correct
14 Correct 135 ms 31180 KB Output is correct
15 Correct 390 ms 41408 KB Output is correct
16 Correct 458 ms 39024 KB Output is correct
17 Correct 395 ms 44156 KB Output is correct
18 Correct 429 ms 43040 KB Output is correct
19 Correct 185 ms 37192 KB Output is correct
20 Correct 182 ms 38760 KB Output is correct
21 Correct 198 ms 37876 KB Output is correct
22 Correct 177 ms 38672 KB Output is correct
23 Correct 188 ms 38320 KB Output is correct
24 Correct 194 ms 37028 KB Output is correct
25 Correct 176 ms 38032 KB Output is correct
26 Correct 200 ms 36600 KB Output is correct
27 Correct 1 ms 724 KB Output is correct
28 Correct 1 ms 724 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 2 ms 724 KB Output is correct
33 Correct 2 ms 724 KB Output is correct
34 Correct 1 ms 704 KB Output is correct
35 Correct 1 ms 724 KB Output is correct
36 Correct 14 ms 5588 KB Output is correct
37 Correct 149 ms 42472 KB Output is correct
38 Correct 150 ms 40380 KB Output is correct
39 Correct 158 ms 38912 KB Output is correct
40 Correct 135 ms 37964 KB Output is correct
41 Correct 134 ms 37468 KB Output is correct
42 Correct 118 ms 34628 KB Output is correct
43 Correct 155 ms 41264 KB Output is correct
44 Correct 156 ms 41832 KB Output is correct
45 Correct 140 ms 42812 KB Output is correct
46 Correct 130 ms 39000 KB Output is correct
47 Correct 21 ms 5464 KB Output is correct
48 Correct 472 ms 44760 KB Output is correct
49 Correct 411 ms 43608 KB Output is correct
50 Correct 446 ms 42828 KB Output is correct
51 Correct 431 ms 42156 KB Output is correct
52 Correct 320 ms 39628 KB Output is correct
53 Correct 281 ms 30992 KB Output is correct
54 Correct 430 ms 44960 KB Output is correct
55 Correct 403 ms 45248 KB Output is correct
56 Correct 406 ms 47216 KB Output is correct
57 Correct 309 ms 43236 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 704 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 113 ms 31740 KB Output is correct
11 Correct 158 ms 39836 KB Output is correct
12 Correct 154 ms 38716 KB Output is correct
13 Correct 168 ms 41156 KB Output is correct
14 Correct 149 ms 42604 KB Output is correct
15 Correct 135 ms 31180 KB Output is correct
16 Correct 390 ms 41408 KB Output is correct
17 Correct 458 ms 39024 KB Output is correct
18 Correct 395 ms 44156 KB Output is correct
19 Correct 429 ms 43040 KB Output is correct
20 Correct 185 ms 37192 KB Output is correct
21 Correct 182 ms 38760 KB Output is correct
22 Correct 198 ms 37876 KB Output is correct
23 Correct 177 ms 38672 KB Output is correct
24 Correct 188 ms 38320 KB Output is correct
25 Correct 194 ms 37028 KB Output is correct
26 Correct 176 ms 38032 KB Output is correct
27 Correct 200 ms 36600 KB Output is correct
28 Correct 1 ms 724 KB Output is correct
29 Correct 1 ms 724 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 2 ms 724 KB Output is correct
34 Correct 2 ms 724 KB Output is correct
35 Correct 1 ms 704 KB Output is correct
36 Correct 1 ms 724 KB Output is correct
37 Correct 14 ms 5588 KB Output is correct
38 Correct 149 ms 42472 KB Output is correct
39 Correct 150 ms 40380 KB Output is correct
40 Correct 158 ms 38912 KB Output is correct
41 Correct 135 ms 37964 KB Output is correct
42 Correct 134 ms 37468 KB Output is correct
43 Correct 118 ms 34628 KB Output is correct
44 Correct 155 ms 41264 KB Output is correct
45 Correct 156 ms 41832 KB Output is correct
46 Correct 140 ms 42812 KB Output is correct
47 Correct 130 ms 39000 KB Output is correct
48 Correct 21 ms 5464 KB Output is correct
49 Correct 472 ms 44760 KB Output is correct
50 Correct 411 ms 43608 KB Output is correct
51 Correct 446 ms 42828 KB Output is correct
52 Correct 431 ms 42156 KB Output is correct
53 Correct 320 ms 39628 KB Output is correct
54 Correct 281 ms 30992 KB Output is correct
55 Correct 430 ms 44960 KB Output is correct
56 Correct 403 ms 45248 KB Output is correct
57 Correct 406 ms 47216 KB Output is correct
58 Correct 309 ms 43236 KB Output is correct
59 Correct 85 ms 10384 KB Output is correct
60 Correct 449 ms 41168 KB Output is correct
61 Correct 422 ms 39236 KB Output is correct
62 Correct 436 ms 42684 KB Output is correct
63 Correct 415 ms 43048 KB Output is correct
64 Correct 1 ms 572 KB Output is correct
65 Correct 1 ms 724 KB Output is correct
66 Correct 1 ms 596 KB Output is correct
67 Correct 1 ms 468 KB Output is correct
68 Correct 1 ms 596 KB Output is correct
69 Correct 2 ms 704 KB Output is correct
70 Correct 2 ms 852 KB Output is correct
71 Correct 2 ms 724 KB Output is correct
72 Correct 2 ms 724 KB Output is correct
73 Correct 2 ms 724 KB Output is correct
74 Correct 142 ms 34552 KB Output is correct
75 Correct 155 ms 39588 KB Output is correct
76 Correct 128 ms 38076 KB Output is correct
77 Correct 124 ms 38060 KB Output is correct
78 Correct 60 ms 9008 KB Output is correct
79 Correct 50 ms 9292 KB Output is correct
80 Correct 105 ms 28576 KB Output is correct
81 Correct 195 ms 43272 KB Output is correct
82 Correct 164 ms 43852 KB Output is correct
83 Correct 194 ms 46640 KB Output is correct
84 Correct 176 ms 43940 KB Output is correct
85 Correct 177 ms 42956 KB Output is correct
86 Correct 83 ms 14284 KB Output is correct
87 Correct 423 ms 43344 KB Output is correct
88 Correct 477 ms 43316 KB Output is correct
89 Correct 288 ms 39792 KB Output is correct
90 Correct 142 ms 13000 KB Output is correct
91 Correct 151 ms 15640 KB Output is correct
92 Correct 269 ms 32204 KB Output is correct
93 Correct 440 ms 47436 KB Output is correct
94 Correct 314 ms 47560 KB Output is correct
95 Correct 465 ms 50420 KB Output is correct
96 Correct 428 ms 45616 KB Output is correct
97 Correct 291 ms 44728 KB Output is correct