oj.uz

Submission #982527

# Submission time Handle Problem Language Result Execution time Memory
982527 2024-05-14T10:49:04 Z phoenix Swapping Cities (APIO20_swap) C++17
100 / 100
 274 ms 58560 KB 
#include <bits/stdc++.h>
#include "swap.h"

using namespace std;
using ll = long long;

const int N = 300300;

const int INF = 1e9;

struct edge {
    int u;
    int v;
    int w;
};  

int bg[N];
int en[N];
int cap[N];
bool isbam[N];
int head[N];
int par[N][18];


vector<edge> edges;

int find(int x) {
    return head[x] = (head[x] == x ? x : find(head[x]));
};

vector<int> g[N];
int tin[N], tout[N], T;

void dfs(int s) {
    tin[s] = ++T;
    for (int to : g[s]) {
        dfs(to);
    }
    tout[s] = T;
}

bool up(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; i++) {
        edges.push_back({U[i], V[i], W[i]});
    }
    
    sort(edges.begin(), edges.end(), [](edge x, edge y) {
        return x.w < y.w;
    });

    int lst = N - 1;
    for (int i = 0; i < N; i++) {
        bg[i] = en[i] = i;
        head[i] = i;
        isbam[i] = true;
    }
    for (auto e : edges) {
        lst++;
        int t1 = find(e.u);
        int t2 = find(e.v);

        head[lst] = par[lst][0] = lst;
        par[t1][0] = par[t2][0] = lst;
        head[t1] = head[t2] = lst;
        cap[lst] = e.w;

        if (t1 == t2) {
            bg[lst] = bg[t1];
            en[lst] = en[t1];
            isbam[lst] = false;
        } else {
            int ar[2][2] = {{bg[t1], en[t1]}, {bg[t2], en[t2]}}; 
            
            bool flag = true; 
            for (int bit_0 = 0; bit_0 < 2 && flag; bit_0++) {
                for (int bit_1 = 0; bit_1 < 2; bit_1++) {
                    if (e.u == ar[0][bit_0] && e.v == ar[1][bit_1]) {
                        bg[lst] = ar[0][!bit_0];
                        en[lst] = ar[1][!bit_1];
                        flag = false;
                        break;
                    }
                    if (e.v == ar[0][bit_0] && e.u == ar[1][bit_1]) {
                        bg[lst] = ar[0][!bit_0];
                        en[lst] = ar[1][!bit_1];
                        flag = false;
                        break;
                    }
                } 
            }
            if (flag) 
                isbam[lst] = false;
            else 
                isbam[lst] = (isbam[t1] & isbam[t2]);
        }
    }
    par[lst][0] = lst;
    for (int i = lst; i >= 0; i--) {
        for (int k = 1; k < 18; k++) {
            par[i][k] = par[ par[i][k - 1] ][k - 1];
        }
        if (par[i][0] != i)
            g[par[i][0]].push_back(i);
    }

    dfs(lst);
}

int getMinimumFuelCapacity(int X, int Y) {
    for (int i = 17; i >= 0; i--) {
        if (!up(par[X][i], Y) || isbam[par[X][i]])
            X = par[X][i];
    }
    if (up(par[X][0], Y) && !isbam[par[X][0]]) {
        X = par[X][0];
        return cap[X];
    }
    return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 59 ms 32476 KB Output is correct
10 Correct 77 ms 39644 KB Output is correct
11 Correct 82 ms 37460 KB Output is correct
12 Correct 75 ms 39944 KB Output is correct
13 Correct 83 ms 41416 KB Output is correct
14 Correct 65 ms 34368 KB Output is correct
15 Correct 145 ms 43092 KB Output is correct
16 Correct 142 ms 40824 KB Output is correct
17 Correct 147 ms 43612 KB Output is correct
18 Correct 156 ms 44848 KB Output is correct
19 Correct 67 ms 25108 KB Output is correct
20 Correct 161 ms 44356 KB Output is correct
21 Correct 146 ms 42336 KB Output is correct
22 Correct 167 ms 45360 KB Output is correct
23 Correct 181 ms 46372 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 171 ms 41068 KB Output is correct
4 Correct 183 ms 46896 KB Output is correct
5 Correct 183 ms 46684 KB Output is correct
6 Correct 179 ms 46668 KB Output is correct
7 Correct 178 ms 46852 KB Output is correct
8 Correct 172 ms 44240 KB Output is correct
9 Correct 187 ms 46620 KB Output is correct
10 Correct 176 ms 44420 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 4 ms 16732 KB Output is correct
13 Correct 3 ms 16728 KB Output is correct
14 Correct 3 ms 16732 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 4 ms 16812 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 4 ms 16820 KB Output is correct
22 Correct 4 ms 16988 KB Output is correct
23 Correct 3 ms 16728 KB Output is correct
24 Correct 4 ms 16988 KB Output is correct
25 Correct 4 ms 16988 KB Output is correct
26 Correct 4 ms 16988 KB Output is correct
27 Correct 4 ms 16756 KB Output is correct
28 Correct 4 ms 16988 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 59 ms 32476 KB Output is correct
11 Correct 77 ms 39644 KB Output is correct
12 Correct 82 ms 37460 KB Output is correct
13 Correct 75 ms 39944 KB Output is correct
14 Correct 83 ms 41416 KB Output is correct
15 Correct 3 ms 16732 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 4 ms 16732 KB Output is correct
18 Correct 3 ms 16728 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 3 ms 16732 KB Output is correct
22 Correct 3 ms 16732 KB Output is correct
23 Correct 3 ms 16732 KB Output is correct
24 Correct 4 ms 16812 KB Output is correct
25 Correct 3 ms 16732 KB Output is correct
26 Correct 4 ms 16820 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 3 ms 16728 KB Output is correct
29 Correct 4 ms 16988 KB Output is correct
30 Correct 4 ms 16988 KB Output is correct
31 Correct 4 ms 16988 KB Output is correct
32 Correct 4 ms 16756 KB Output is correct
33 Correct 4 ms 16988 KB Output is correct
34 Correct 12 ms 19996 KB Output is correct
35 Correct 75 ms 39876 KB Output is correct
36 Correct 93 ms 39876 KB Output is correct
37 Correct 76 ms 39732 KB Output is correct
38 Correct 76 ms 39612 KB Output is correct
39 Correct 76 ms 39368 KB Output is correct
40 Correct 71 ms 36804 KB Output is correct
41 Correct 77 ms 40132 KB Output is correct
42 Correct 77 ms 39876 KB Output is correct
43 Correct 82 ms 41416 KB Output is correct
44 Correct 84 ms 40136 KB Output is correct
45 Correct 122 ms 48864 KB Output is correct
46 Correct 74 ms 39880 KB Output is correct
47 Correct 89 ms 39960 KB Output is correct
48 Correct 105 ms 41612 KB Output is correct
49 Correct 77 ms 44056 KB Output is correct
50 Correct 62 ms 38440 KB Output is correct
51 Correct 120 ms 44620 KB Output is correct
52 Correct 118 ms 51172 KB Output is correct
53 Correct 158 ms 52160 KB Output is correct
54 Correct 138 ms 55492 KB Output is correct
55 Correct 110 ms 41552 KB Output is correct
56 Correct 153 ms 53752 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 59 ms 32476 KB Output is correct
10 Correct 77 ms 39644 KB Output is correct
11 Correct 82 ms 37460 KB Output is correct
12 Correct 75 ms 39944 KB Output is correct
13 Correct 83 ms 41416 KB Output is correct
14 Correct 65 ms 34368 KB Output is correct
15 Correct 145 ms 43092 KB Output is correct
16 Correct 142 ms 40824 KB Output is correct
17 Correct 147 ms 43612 KB Output is correct
18 Correct 156 ms 44848 KB Output is correct
19 Correct 171 ms 41068 KB Output is correct
20 Correct 183 ms 46896 KB Output is correct
21 Correct 183 ms 46684 KB Output is correct
22 Correct 179 ms 46668 KB Output is correct
23 Correct 178 ms 46852 KB Output is correct
24 Correct 172 ms 44240 KB Output is correct
25 Correct 187 ms 46620 KB Output is correct
26 Correct 176 ms 44420 KB Output is correct
27 Correct 3 ms 16732 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 4 ms 16732 KB Output is correct
30 Correct 3 ms 16728 KB Output is correct
31 Correct 3 ms 16732 KB Output is correct
32 Correct 3 ms 16732 KB Output is correct
33 Correct 3 ms 16732 KB Output is correct
34 Correct 3 ms 16732 KB Output is correct
35 Correct 3 ms 16732 KB Output is correct
36 Correct 12 ms 19996 KB Output is correct
37 Correct 75 ms 39876 KB Output is correct
38 Correct 93 ms 39876 KB Output is correct
39 Correct 76 ms 39732 KB Output is correct
40 Correct 76 ms 39612 KB Output is correct
41 Correct 76 ms 39368 KB Output is correct
42 Correct 71 ms 36804 KB Output is correct
43 Correct 77 ms 40132 KB Output is correct
44 Correct 77 ms 39876 KB Output is correct
45 Correct 82 ms 41416 KB Output is correct
46 Correct 84 ms 40136 KB Output is correct
47 Correct 18 ms 20608 KB Output is correct
48 Correct 151 ms 44168 KB Output is correct
49 Correct 158 ms 44188 KB Output is correct
50 Correct 155 ms 44072 KB Output is correct
51 Correct 158 ms 44148 KB Output is correct
52 Correct 162 ms 41588 KB Output is correct
53 Correct 131 ms 38180 KB Output is correct
54 Correct 153 ms 45100 KB Output is correct
55 Correct 156 ms 44124 KB Output is correct
56 Correct 182 ms 45656 KB Output is correct
57 Correct 168 ms 45100 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 59 ms 32476 KB Output is correct
11 Correct 77 ms 39644 KB Output is correct
12 Correct 82 ms 37460 KB Output is correct
13 Correct 75 ms 39944 KB Output is correct
14 Correct 83 ms 41416 KB Output is correct
15 Correct 65 ms 34368 KB Output is correct
16 Correct 145 ms 43092 KB Output is correct
17 Correct 142 ms 40824 KB Output is correct
18 Correct 147 ms 43612 KB Output is correct
19 Correct 156 ms 44848 KB Output is correct
20 Correct 171 ms 41068 KB Output is correct
21 Correct 183 ms 46896 KB Output is correct
22 Correct 183 ms 46684 KB Output is correct
23 Correct 179 ms 46668 KB Output is correct
24 Correct 178 ms 46852 KB Output is correct
25 Correct 172 ms 44240 KB Output is correct
26 Correct 187 ms 46620 KB Output is correct
27 Correct 176 ms 44420 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 3 ms 16732 KB Output is correct
30 Correct 4 ms 16732 KB Output is correct
31 Correct 3 ms 16728 KB Output is correct
32 Correct 3 ms 16732 KB Output is correct
33 Correct 3 ms 16732 KB Output is correct
34 Correct 3 ms 16732 KB Output is correct
35 Correct 3 ms 16732 KB Output is correct
36 Correct 3 ms 16732 KB Output is correct
37 Correct 12 ms 19996 KB Output is correct
38 Correct 75 ms 39876 KB Output is correct
39 Correct 93 ms 39876 KB Output is correct
40 Correct 76 ms 39732 KB Output is correct
41 Correct 76 ms 39612 KB Output is correct
42 Correct 76 ms 39368 KB Output is correct
43 Correct 71 ms 36804 KB Output is correct
44 Correct 77 ms 40132 KB Output is correct
45 Correct 77 ms 39876 KB Output is correct
46 Correct 82 ms 41416 KB Output is correct
47 Correct 84 ms 40136 KB Output is correct
48 Correct 18 ms 20608 KB Output is correct
49 Correct 151 ms 44168 KB Output is correct
50 Correct 158 ms 44188 KB Output is correct
51 Correct 155 ms 44072 KB Output is correct
52 Correct 158 ms 44148 KB Output is correct
53 Correct 162 ms 41588 KB Output is correct
54 Correct 131 ms 38180 KB Output is correct
55 Correct 153 ms 45100 KB Output is correct
56 Correct 156 ms 44124 KB Output is correct
57 Correct 182 ms 45656 KB Output is correct
58 Correct 168 ms 45100 KB Output is correct
59 Correct 67 ms 25108 KB Output is correct
60 Correct 161 ms 44356 KB Output is correct
61 Correct 146 ms 42336 KB Output is correct
62 Correct 167 ms 45360 KB Output is correct
63 Correct 181 ms 46372 KB Output is correct
64 Correct 4 ms 16812 KB Output is correct
65 Correct 3 ms 16732 KB Output is correct
66 Correct 4 ms 16820 KB Output is correct
67 Correct 4 ms 16988 KB Output is correct
68 Correct 3 ms 16728 KB Output is correct
69 Correct 4 ms 16988 KB Output is correct
70 Correct 4 ms 16988 KB Output is correct
71 Correct 4 ms 16988 KB Output is correct
72 Correct 4 ms 16756 KB Output is correct
73 Correct 4 ms 16988 KB Output is correct
74 Correct 122 ms 48864 KB Output is correct
75 Correct 74 ms 39880 KB Output is correct
76 Correct 89 ms 39960 KB Output is correct
77 Correct 105 ms 41612 KB Output is correct
78 Correct 77 ms 44056 KB Output is correct
79 Correct 62 ms 38440 KB Output is correct
80 Correct 120 ms 44620 KB Output is correct
81 Correct 118 ms 51172 KB Output is correct
82 Correct 158 ms 52160 KB Output is correct
83 Correct 138 ms 55492 KB Output is correct
84 Correct 110 ms 41552 KB Output is correct
85 Correct 153 ms 53752 KB Output is correct
86 Correct 61 ms 29128 KB Output is correct
87 Correct 152 ms 44332 KB Output is correct
88 Correct 153 ms 44076 KB Output is correct
89 Correct 194 ms 45676 KB Output is correct
90 Correct 160 ms 50516 KB Output is correct
91 Correct 166 ms 47800 KB Output is correct
92 Correct 197 ms 46080 KB Output is correct
93 Correct 203 ms 55892 KB Output is correct
94 Correct 274 ms 56748 KB Output is correct
95 Correct 213 ms 58560 KB Output is correct
96 Correct 186 ms 45612 KB Output is correct
97 Correct 230 ms 52036 KB Output is correct