oj.uz

Submission #894746

# Submission time Handle Problem Language Result Execution time Memory
894746 2023-12-28T20:54:53 Z ShaShi Swapping Cities (APIO20_swap) C++17
100 / 100
 221 ms 70724 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
 
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const int LG = 18;
const int MOD = 998244353;
const int INF = (int)1e18 + 7;
 
 
 
int n, m, t, flag, k, u, v, w, ans, ans2, tmp, tmp2, tmp3, tmp4, q, timer;
int arr[MAXN], num[MAXN];
int par[MAXN], love[MAXN], dp[MAXN], deg[MAXN];
int h[MAXN], dad[MAXN], pow2dad[MAXN][LG];
vector<pair<int, pii> > edge;
vector<int> adj[MAXN];
 
 
/* DSU */
 
inline int get_par(int v) {
    return (par[v] == v? v : par[v] = get_par(par[v]));
}
 
 
void unite(int u, int v, int w) {
    int u2, v2;
    u2 = u;
    v2 = v;
 
    deg[u2]++, deg[v2]++;
 
    u = get_par(u), v = get_par(v);
 
    if (u == v) {
        if (!love[u]) {
            love[u] = 1;
            num[u] = w;
        }
    } else {
        par[u] = par[v] = flag;
        par[flag] = flag;
        adj[flag].pb(u), adj[flag].pb(v);
        num[flag] = w;
 
        if (love[u] || love[v]) {
            love[flag] = 1;
        } else {
            love[flag] = (deg[u2] == 3 || deg[v2] == 3);
        }
 
        // cout << "@" << flag << " " << u << " " << v << endl;
 
        flag++;
    }
 
}
 
/* DSU */
 
/* LCA */
 
inline int up(int v, int k) {
    for (int i=LG-1; i>=0; i--) {
        if ((1<<i) <= k) {
            k -= (1<<i);
            v = pow2dad[v][i];
        }
    }
 
    return v;
}
 
 
int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
 
    u = up(u, h[u]-h[v]);
 
    for (int i=LG-1; i>=0; i--) {
        if (h[v] >= (1<<i) && pow2dad[v][i] != pow2dad[u][i]) {
            v = pow2dad[v][i];
            u = pow2dad[u][i];
        }
    }
 
    if (u == v) return u;
    return dad[v];
}
 
 
/* LCA */
 
 
// void DFS(int v) {
//     for (int u:adj[v]) {
//         if (u != dad[v]) {
//             dad[u] = v;
//             h[u] = h[v]+1;
//             DFS(u);
 
//             love[v] |= love[u];
//         }
//     }
 
//     dp[v] = (love[v]? v : dp[dad[v]]);
// }
 
void DFS(int v) {
    dp[v] = (love[v]? v : dp[dad[v]]);
 
    for (int u:adj[v]) {
        if (u != dad[v]) {
            dad[u] = v;
            h[u] = h[v]+1;
            DFS(u);
        }
    }
}
 
 
 
void DFS2(int v) {
    dp[v] = (love[v]? v : dp[dad[v]]);
 
    for (int u:adj[v]) if (u != dad[v]) DFS2(u);
}
 
 
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++) {
        // cin >> u >> v >> w;
		u = U[i]+1;
		v = V[i]+1;
		w = W[i];
 
        edge.pb(mp(w, mp(u, v)));
    }
 
    sort(all(edge));
    flag = n+1;
 
    for (int i=1; i<=n; i++) par[i] = i;
    
    for (int i=0; i<m; i++) unite(edge[i].S.F, edge[i].S.S, edge[i].F);
    flag--;
 
    DFS(flag);
    // DFS2(flag);
 
    for (int i=1; i<=flag; i++) pow2dad[i][0] = dad[i];
    for (int j=1; j<LG; j++) for (int i=1; i<=flag; i++) pow2dad[i][j] = pow2dad[pow2dad[i][j-1]][j-1];
    num[0]--;
}
 
int getMinimumFuelCapacity(int X, int Y) {
	return num[dp[LCA(X+1, Y+1)]];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31508 KB Output is correct
7 Correct 6 ms 31320 KB Output is correct
8 Correct 7 ms 31320 KB Output is correct
9 Correct 48 ms 48836 KB Output is correct
10 Correct 65 ms 53956 KB Output is correct
11 Correct 59 ms 53868 KB Output is correct
12 Correct 64 ms 56516 KB Output is correct
13 Correct 61 ms 59592 KB Output is correct
14 Correct 55 ms 49028 KB Output is correct
15 Correct 144 ms 57860 KB Output is correct
16 Correct 120 ms 55672 KB Output is correct
17 Correct 142 ms 58212 KB Output is correct
18 Correct 173 ms 61432 KB Output is correct
19 Correct 63 ms 40288 KB Output is correct
20 Correct 126 ms 60416 KB Output is correct
21 Correct 128 ms 58304 KB Output is correct
22 Correct 126 ms 60968 KB Output is correct
23 Correct 167 ms 64044 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 163 ms 64100 KB Output is correct
4 Correct 158 ms 70704 KB Output is correct
5 Correct 144 ms 68592 KB Output is correct
6 Correct 145 ms 70444 KB Output is correct
7 Correct 152 ms 70724 KB Output is correct
8 Correct 171 ms 67960 KB Output is correct
9 Correct 177 ms 70472 KB Output is correct
10 Correct 144 ms 67804 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31508 KB Output is correct
7 Correct 6 ms 31320 KB Output is correct
8 Correct 7 ms 31320 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 8 ms 33420 KB Output is correct
12 Correct 7 ms 33372 KB Output is correct
13 Correct 7 ms 33372 KB Output is correct
14 Correct 7 ms 33372 KB Output is correct
15 Correct 7 ms 33780 KB Output is correct
16 Correct 7 ms 33416 KB Output is correct
17 Correct 7 ms 33368 KB Output is correct
18 Correct 7 ms 33372 KB Output is correct
19 Correct 7 ms 33540 KB Output is correct
20 Correct 7 ms 33416 KB Output is correct
21 Correct 7 ms 33368 KB Output is correct
22 Correct 7 ms 33368 KB Output is correct
23 Correct 7 ms 33372 KB Output is correct
24 Correct 7 ms 33372 KB Output is correct
25 Correct 7 ms 33368 KB Output is correct
26 Correct 7 ms 33372 KB Output is correct
27 Correct 7 ms 33372 KB Output is correct
28 Correct 7 ms 33392 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31508 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Correct 7 ms 31320 KB Output is correct
10 Correct 48 ms 48836 KB Output is correct
11 Correct 65 ms 53956 KB Output is correct
12 Correct 59 ms 53868 KB Output is correct
13 Correct 64 ms 56516 KB Output is correct
14 Correct 61 ms 59592 KB Output is correct
15 Correct 7 ms 33372 KB Output is correct
16 Correct 8 ms 33420 KB Output is correct
17 Correct 7 ms 33372 KB Output is correct
18 Correct 7 ms 33372 KB Output is correct
19 Correct 7 ms 33372 KB Output is correct
20 Correct 7 ms 33780 KB Output is correct
21 Correct 7 ms 33416 KB Output is correct
22 Correct 7 ms 33368 KB Output is correct
23 Correct 7 ms 33372 KB Output is correct
24 Correct 7 ms 33540 KB Output is correct
25 Correct 7 ms 33416 KB Output is correct
26 Correct 7 ms 33368 KB Output is correct
27 Correct 7 ms 33368 KB Output is correct
28 Correct 7 ms 33372 KB Output is correct
29 Correct 7 ms 33372 KB Output is correct
30 Correct 7 ms 33368 KB Output is correct
31 Correct 7 ms 33372 KB Output is correct
32 Correct 7 ms 33372 KB Output is correct
33 Correct 7 ms 33392 KB Output is correct
34 Correct 14 ms 36636 KB Output is correct
35 Correct 63 ms 57628 KB Output is correct
36 Correct 67 ms 57832 KB Output is correct
37 Correct 62 ms 57720 KB Output is correct
38 Correct 64 ms 57544 KB Output is correct
39 Correct 64 ms 57540 KB Output is correct
40 Correct 57 ms 54832 KB Output is correct
41 Correct 77 ms 58276 KB Output is correct
42 Correct 75 ms 57796 KB Output is correct
43 Correct 62 ms 61892 KB Output is correct
44 Correct 66 ms 57796 KB Output is correct
45 Correct 79 ms 54212 KB Output is correct
46 Correct 63 ms 57832 KB Output is correct
47 Correct 64 ms 57796 KB Output is correct
48 Correct 73 ms 59672 KB Output is correct
49 Correct 56 ms 39104 KB Output is correct
50 Correct 50 ms 38024 KB Output is correct
51 Correct 67 ms 50628 KB Output is correct
52 Correct 85 ms 60100 KB Output is correct
53 Correct 91 ms 61376 KB Output is correct
54 Correct 101 ms 61904 KB Output is correct
55 Correct 58 ms 61572 KB Output is correct
56 Correct 92 ms 62144 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31508 KB Output is correct
7 Correct 6 ms 31320 KB Output is correct
8 Correct 7 ms 31320 KB Output is correct
9 Correct 48 ms 48836 KB Output is correct
10 Correct 65 ms 53956 KB Output is correct
11 Correct 59 ms 53868 KB Output is correct
12 Correct 64 ms 56516 KB Output is correct
13 Correct 61 ms 59592 KB Output is correct
14 Correct 55 ms 49028 KB Output is correct
15 Correct 144 ms 57860 KB Output is correct
16 Correct 120 ms 55672 KB Output is correct
17 Correct 142 ms 58212 KB Output is correct
18 Correct 173 ms 61432 KB Output is correct
19 Correct 163 ms 64100 KB Output is correct
20 Correct 158 ms 70704 KB Output is correct
21 Correct 144 ms 68592 KB Output is correct
22 Correct 145 ms 70444 KB Output is correct
23 Correct 152 ms 70724 KB Output is correct
24 Correct 171 ms 67960 KB Output is correct
25 Correct 177 ms 70472 KB Output is correct
26 Correct 144 ms 67804 KB Output is correct
27 Correct 7 ms 33372 KB Output is correct
28 Correct 8 ms 33420 KB Output is correct
29 Correct 7 ms 33372 KB Output is correct
30 Correct 7 ms 33372 KB Output is correct
31 Correct 7 ms 33372 KB Output is correct
32 Correct 7 ms 33780 KB Output is correct
33 Correct 7 ms 33416 KB Output is correct
34 Correct 7 ms 33368 KB Output is correct
35 Correct 7 ms 33372 KB Output is correct
36 Correct 14 ms 36636 KB Output is correct
37 Correct 63 ms 57628 KB Output is correct
38 Correct 67 ms 57832 KB Output is correct
39 Correct 62 ms 57720 KB Output is correct
40 Correct 64 ms 57544 KB Output is correct
41 Correct 64 ms 57540 KB Output is correct
42 Correct 57 ms 54832 KB Output is correct
43 Correct 77 ms 58276 KB Output is correct
44 Correct 75 ms 57796 KB Output is correct
45 Correct 62 ms 61892 KB Output is correct
46 Correct 66 ms 57796 KB Output is correct
47 Correct 24 ms 37252 KB Output is correct
48 Correct 162 ms 64556 KB Output is correct
49 Correct 127 ms 64384 KB Output is correct
50 Correct 152 ms 64384 KB Output is correct
51 Correct 131 ms 64404 KB Output is correct
52 Correct 159 ms 61708 KB Output is correct
53 Correct 126 ms 54456 KB Output is correct
54 Correct 136 ms 65556 KB Output is correct
55 Correct 145 ms 64384 KB Output is correct
56 Correct 170 ms 67700 KB Output is correct
57 Correct 165 ms 65292 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 6 ms 31508 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Correct 7 ms 31320 KB Output is correct
10 Correct 48 ms 48836 KB Output is correct
11 Correct 65 ms 53956 KB Output is correct
12 Correct 59 ms 53868 KB Output is correct
13 Correct 64 ms 56516 KB Output is correct
14 Correct 61 ms 59592 KB Output is correct
15 Correct 55 ms 49028 KB Output is correct
16 Correct 144 ms 57860 KB Output is correct
17 Correct 120 ms 55672 KB Output is correct
18 Correct 142 ms 58212 KB Output is correct
19 Correct 173 ms 61432 KB Output is correct
20 Correct 163 ms 64100 KB Output is correct
21 Correct 158 ms 70704 KB Output is correct
22 Correct 144 ms 68592 KB Output is correct
23 Correct 145 ms 70444 KB Output is correct
24 Correct 152 ms 70724 KB Output is correct
25 Correct 171 ms 67960 KB Output is correct
26 Correct 177 ms 70472 KB Output is correct
27 Correct 144 ms 67804 KB Output is correct
28 Correct 7 ms 33372 KB Output is correct
29 Correct 8 ms 33420 KB Output is correct
30 Correct 7 ms 33372 KB Output is correct
31 Correct 7 ms 33372 KB Output is correct
32 Correct 7 ms 33372 KB Output is correct
33 Correct 7 ms 33780 KB Output is correct
34 Correct 7 ms 33416 KB Output is correct
35 Correct 7 ms 33368 KB Output is correct
36 Correct 7 ms 33372 KB Output is correct
37 Correct 14 ms 36636 KB Output is correct
38 Correct 63 ms 57628 KB Output is correct
39 Correct 67 ms 57832 KB Output is correct
40 Correct 62 ms 57720 KB Output is correct
41 Correct 64 ms 57544 KB Output is correct
42 Correct 64 ms 57540 KB Output is correct
43 Correct 57 ms 54832 KB Output is correct
44 Correct 77 ms 58276 KB Output is correct
45 Correct 75 ms 57796 KB Output is correct
46 Correct 62 ms 61892 KB Output is correct
47 Correct 66 ms 57796 KB Output is correct
48 Correct 24 ms 37252 KB Output is correct
49 Correct 162 ms 64556 KB Output is correct
50 Correct 127 ms 64384 KB Output is correct
51 Correct 152 ms 64384 KB Output is correct
52 Correct 131 ms 64404 KB Output is correct
53 Correct 159 ms 61708 KB Output is correct
54 Correct 126 ms 54456 KB Output is correct
55 Correct 136 ms 65556 KB Output is correct
56 Correct 145 ms 64384 KB Output is correct
57 Correct 170 ms 67700 KB Output is correct
58 Correct 165 ms 65292 KB Output is correct
59 Correct 63 ms 40288 KB Output is correct
60 Correct 126 ms 60416 KB Output is correct
61 Correct 128 ms 58304 KB Output is correct
62 Correct 126 ms 60968 KB Output is correct
63 Correct 167 ms 64044 KB Output is correct
64 Correct 7 ms 33540 KB Output is correct
65 Correct 7 ms 33416 KB Output is correct
66 Correct 7 ms 33368 KB Output is correct
67 Correct 7 ms 33368 KB Output is correct
68 Correct 7 ms 33372 KB Output is correct
69 Correct 7 ms 33372 KB Output is correct
70 Correct 7 ms 33368 KB Output is correct
71 Correct 7 ms 33372 KB Output is correct
72 Correct 7 ms 33372 KB Output is correct
73 Correct 7 ms 33392 KB Output is correct
74 Correct 79 ms 54212 KB Output is correct
75 Correct 63 ms 57832 KB Output is correct
76 Correct 64 ms 57796 KB Output is correct
77 Correct 73 ms 59672 KB Output is correct
78 Correct 56 ms 39104 KB Output is correct
79 Correct 50 ms 38024 KB Output is correct
80 Correct 67 ms 50628 KB Output is correct
81 Correct 85 ms 60100 KB Output is correct
82 Correct 91 ms 61376 KB Output is correct
83 Correct 101 ms 61904 KB Output is correct
84 Correct 58 ms 61572 KB Output is correct
85 Correct 92 ms 62144 KB Output is correct
86 Correct 52 ms 43468 KB Output is correct
87 Correct 139 ms 64400 KB Output is correct
88 Correct 147 ms 64532 KB Output is correct
89 Correct 174 ms 63720 KB Output is correct
90 Correct 123 ms 46868 KB Output is correct
91 Correct 130 ms 49892 KB Output is correct
92 Correct 141 ms 58144 KB Output is correct
93 Correct 176 ms 68224 KB Output is correct
94 Correct 192 ms 69244 KB Output is correct
95 Correct 203 ms 69532 KB Output is correct
96 Correct 207 ms 67888 KB Output is correct
97 Correct 221 ms 68500 KB Output is correct