oj.uz

Submission #871346

# Submission time Handle Problem Language Result Execution time Memory
871346 2023-11-10T15:38:32 Z serifefedartar Swapping Cities (APIO20_swap) C++17
100 / 100
 328 ms 64600 KB 
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 22; 
const ll MAXN = 1e5 + 100;
 
int par[3 * MAXN], deg[3 * MAXN], w[3 * MAXN], nds;
int depth[3 * MAXN], up[LOGN][3 * MAXN];
bool reach[3 * MAXN];
vector<pair<int,pair<int,int>>> edges;
vector<vector<int>> graph;
int find(int node) {
	if (node == par[node])
		return node;
	return par[node] = find(par[node]);
}
 
void addEdge(int u, int v) {
	int old_u = u, old_v = v;
	u = find(u), v = find(v);
	
  	deg[old_u]++, deg[old_v]++;
	par[u] = par[v] = nds;
	graph[nds].push_back(u);
	reach[nds] = reach[u] || reach[v];
	if (u == v)
		reach[nds] = true;
	else {
		graph[nds].push_back(v);
		if (max(deg[old_u], deg[old_v]) > 2)
			reach[nds] = true; 
	}
}
 
void dfs(int node) {
	for (auto u : graph[node]) {
		depth[u] = depth[node] + 1;
		up[0][u] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u] = up[i-1][up[i-1][u]];
		dfs(u);
	}
}
 
int find(int node, int k) {
	for (int i = LOGN-1; i >= 0; i--) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}
 
int lca(int u, int v) {
	if (depth[v] > depth[u])
		swap(u, v);
	u = find(u, depth[u] - depth[v]);
 
	if (u == v)
		return u;
 
	for (int i = LOGN - 1; i >= 0; i--) {
		if (up[i][u] != up[i][v]) {
			u = up[i][u];
			v = up[i][v];
		}
	}
	return up[0][u];
}
 
int first_active(int node) {
	if (reach[node])
		return node;
	for (int i = LOGN - 1; i >= 0; i--) {
		if (reach[up[i][node]] == 0)
			node = up[i][node];
	}
	return up[0][node];
}
 
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	nds = N;
	graph = vector<vector<int>>(N+M+1, vector<int>());
	for (int i = 1; i <= N + M; i++)
		par[i] = i;
	for (int i = 0; i < M; i++)
		edges.push_back({W[i], {U[i] + 1, V[i] + 1}});
	sort(edges.begin(), edges.end());
 
	for (int i = 0; i < M; i++) {
		nds++;
		w[nds] = edges[i].f;
		addEdge(edges[i].s.f, edges[i].s.s);
	}
 
	for (int j = 0; j < LOGN; j++)
		up[j][nds] = nds;
	dfs(nds);
}
 
int getMinimumFuelCapacity(int X, int Y) {
	X++, Y++;
	int Q = first_active(lca(X, Y));
	if (reach[Q])
		return w[Q];
	else
		return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29116 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 4 ms 29128 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 66 ms 39632 KB Output is correct
10 Correct 84 ms 42148 KB Output is correct
11 Correct 83 ms 41856 KB Output is correct
12 Correct 87 ms 42432 KB Output is correct
13 Correct 75 ms 45764 KB Output is correct
14 Correct 73 ms 39972 KB Output is correct
15 Correct 204 ms 44872 KB Output is correct
16 Correct 173 ms 44716 KB Output is correct
17 Correct 206 ms 45640 KB Output is correct
18 Correct 260 ms 48940 KB Output is correct
19 Correct 80 ms 35860 KB Output is correct
20 Correct 180 ms 46208 KB Output is correct
21 Correct 179 ms 45892 KB Output is correct
22 Correct 189 ms 47072 KB Output is correct
23 Correct 237 ms 50240 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 173 ms 51564 KB Output is correct
4 Correct 171 ms 54304 KB Output is correct
5 Correct 192 ms 53916 KB Output is correct
6 Correct 181 ms 54052 KB Output is correct
7 Correct 179 ms 54088 KB Output is correct
8 Correct 185 ms 53380 KB Output is correct
9 Correct 167 ms 53832 KB Output is correct
10 Correct 171 ms 53124 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29116 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 4 ms 29128 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 3 ms 29020 KB Output is correct
10 Correct 4 ms 29276 KB Output is correct
11 Correct 4 ms 29276 KB Output is correct
12 Correct 4 ms 29276 KB Output is correct
13 Correct 3 ms 29120 KB Output is correct
14 Correct 4 ms 29272 KB Output is correct
15 Correct 4 ms 29276 KB Output is correct
16 Correct 4 ms 29276 KB Output is correct
17 Correct 4 ms 29276 KB Output is correct
18 Correct 4 ms 29144 KB Output is correct
19 Correct 4 ms 29276 KB Output is correct
20 Correct 4 ms 29272 KB Output is correct
21 Correct 4 ms 29272 KB Output is correct
22 Correct 4 ms 29276 KB Output is correct
23 Correct 4 ms 29276 KB Output is correct
24 Correct 4 ms 29276 KB Output is correct
25 Correct 4 ms 29320 KB Output is correct
26 Correct 4 ms 29276 KB Output is correct
27 Correct 3 ms 29276 KB Output is correct
28 Correct 4 ms 29276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 3 ms 29116 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 4 ms 29128 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 4 ms 29272 KB Output is correct
10 Correct 66 ms 39632 KB Output is correct
11 Correct 84 ms 42148 KB Output is correct
12 Correct 83 ms 41856 KB Output is correct
13 Correct 87 ms 42432 KB Output is correct
14 Correct 75 ms 45764 KB Output is correct
15 Correct 4 ms 29276 KB Output is correct
16 Correct 4 ms 29276 KB Output is correct
17 Correct 4 ms 29276 KB Output is correct
18 Correct 3 ms 29120 KB Output is correct
19 Correct 4 ms 29272 KB Output is correct
20 Correct 4 ms 29276 KB Output is correct
21 Correct 4 ms 29276 KB Output is correct
22 Correct 4 ms 29276 KB Output is correct
23 Correct 4 ms 29144 KB Output is correct
24 Correct 4 ms 29276 KB Output is correct
25 Correct 4 ms 29272 KB Output is correct
26 Correct 4 ms 29272 KB Output is correct
27 Correct 4 ms 29276 KB Output is correct
28 Correct 4 ms 29276 KB Output is correct
29 Correct 4 ms 29276 KB Output is correct
30 Correct 4 ms 29320 KB Output is correct
31 Correct 4 ms 29276 KB Output is correct
32 Correct 3 ms 29276 KB Output is correct
33 Correct 4 ms 29276 KB Output is correct
34 Correct 12 ms 30896 KB Output is correct
35 Correct 88 ms 42984 KB Output is correct
36 Correct 86 ms 42948 KB Output is correct
37 Correct 87 ms 43200 KB Output is correct
38 Correct 84 ms 42952 KB Output is correct
39 Correct 90 ms 42776 KB Output is correct
40 Correct 79 ms 41808 KB Output is correct
41 Correct 86 ms 43500 KB Output is correct
42 Correct 92 ms 43208 KB Output is correct
43 Correct 74 ms 47300 KB Output is correct
44 Correct 88 ms 43544 KB Output is correct
45 Correct 103 ms 53948 KB Output is correct
46 Correct 90 ms 43208 KB Output is correct
47 Correct 84 ms 43340 KB Output is correct
48 Correct 89 ms 46784 KB Output is correct
49 Correct 78 ms 57276 KB Output is correct
50 Correct 65 ms 50372 KB Output is correct
51 Correct 89 ms 50884 KB Output is correct
52 Correct 126 ms 54348 KB Output is correct
53 Correct 138 ms 56768 KB Output is correct
54 Correct 143 ms 60756 KB Output is correct
55 Correct 78 ms 46964 KB Output is correct
56 Correct 130 ms 57980 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29116 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 4 ms 29128 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 66 ms 39632 KB Output is correct
10 Correct 84 ms 42148 KB Output is correct
11 Correct 83 ms 41856 KB Output is correct
12 Correct 87 ms 42432 KB Output is correct
13 Correct 75 ms 45764 KB Output is correct
14 Correct 73 ms 39972 KB Output is correct
15 Correct 204 ms 44872 KB Output is correct
16 Correct 173 ms 44716 KB Output is correct
17 Correct 206 ms 45640 KB Output is correct
18 Correct 260 ms 48940 KB Output is correct
19 Correct 173 ms 51564 KB Output is correct
20 Correct 171 ms 54304 KB Output is correct
21 Correct 192 ms 53916 KB Output is correct
22 Correct 181 ms 54052 KB Output is correct
23 Correct 179 ms 54088 KB Output is correct
24 Correct 185 ms 53380 KB Output is correct
25 Correct 167 ms 53832 KB Output is correct
26 Correct 171 ms 53124 KB Output is correct
27 Correct 4 ms 29276 KB Output is correct
28 Correct 4 ms 29276 KB Output is correct
29 Correct 4 ms 29276 KB Output is correct
30 Correct 3 ms 29120 KB Output is correct
31 Correct 4 ms 29272 KB Output is correct
32 Correct 4 ms 29276 KB Output is correct
33 Correct 4 ms 29276 KB Output is correct
34 Correct 4 ms 29276 KB Output is correct
35 Correct 4 ms 29144 KB Output is correct
36 Correct 12 ms 30896 KB Output is correct
37 Correct 88 ms 42984 KB Output is correct
38 Correct 86 ms 42948 KB Output is correct
39 Correct 87 ms 43200 KB Output is correct
40 Correct 84 ms 42952 KB Output is correct
41 Correct 90 ms 42776 KB Output is correct
42 Correct 79 ms 41808 KB Output is correct
43 Correct 86 ms 43500 KB Output is correct
44 Correct 92 ms 43208 KB Output is correct
45 Correct 74 ms 47300 KB Output is correct
46 Correct 88 ms 43544 KB Output is correct
47 Correct 18 ms 31256 KB Output is correct
48 Correct 172 ms 47856 KB Output is correct
49 Correct 168 ms 47944 KB Output is correct
50 Correct 162 ms 47952 KB Output is correct
51 Correct 163 ms 47932 KB Output is correct
52 Correct 150 ms 47220 KB Output is correct
53 Correct 126 ms 44336 KB Output is correct
54 Correct 175 ms 48948 KB Output is correct
55 Correct 183 ms 47916 KB Output is correct
56 Correct 189 ms 51244 KB Output is correct
57 Correct 177 ms 48944 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 3 ms 29116 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 4 ms 29128 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 4 ms 29272 KB Output is correct
10 Correct 66 ms 39632 KB Output is correct
11 Correct 84 ms 42148 KB Output is correct
12 Correct 83 ms 41856 KB Output is correct
13 Correct 87 ms 42432 KB Output is correct
14 Correct 75 ms 45764 KB Output is correct
15 Correct 73 ms 39972 KB Output is correct
16 Correct 204 ms 44872 KB Output is correct
17 Correct 173 ms 44716 KB Output is correct
18 Correct 206 ms 45640 KB Output is correct
19 Correct 260 ms 48940 KB Output is correct
20 Correct 173 ms 51564 KB Output is correct
21 Correct 171 ms 54304 KB Output is correct
22 Correct 192 ms 53916 KB Output is correct
23 Correct 181 ms 54052 KB Output is correct
24 Correct 179 ms 54088 KB Output is correct
25 Correct 185 ms 53380 KB Output is correct
26 Correct 167 ms 53832 KB Output is correct
27 Correct 171 ms 53124 KB Output is correct
28 Correct 4 ms 29276 KB Output is correct
29 Correct 4 ms 29276 KB Output is correct
30 Correct 4 ms 29276 KB Output is correct
31 Correct 3 ms 29120 KB Output is correct
32 Correct 4 ms 29272 KB Output is correct
33 Correct 4 ms 29276 KB Output is correct
34 Correct 4 ms 29276 KB Output is correct
35 Correct 4 ms 29276 KB Output is correct
36 Correct 4 ms 29144 KB Output is correct
37 Correct 12 ms 30896 KB Output is correct
38 Correct 88 ms 42984 KB Output is correct
39 Correct 86 ms 42948 KB Output is correct
40 Correct 87 ms 43200 KB Output is correct
41 Correct 84 ms 42952 KB Output is correct
42 Correct 90 ms 42776 KB Output is correct
43 Correct 79 ms 41808 KB Output is correct
44 Correct 86 ms 43500 KB Output is correct
45 Correct 92 ms 43208 KB Output is correct
46 Correct 74 ms 47300 KB Output is correct
47 Correct 88 ms 43544 KB Output is correct
48 Correct 18 ms 31256 KB Output is correct
49 Correct 172 ms 47856 KB Output is correct
50 Correct 168 ms 47944 KB Output is correct
51 Correct 162 ms 47952 KB Output is correct
52 Correct 163 ms 47932 KB Output is correct
53 Correct 150 ms 47220 KB Output is correct
54 Correct 126 ms 44336 KB Output is correct
55 Correct 175 ms 48948 KB Output is correct
56 Correct 183 ms 47916 KB Output is correct
57 Correct 189 ms 51244 KB Output is correct
58 Correct 177 ms 48944 KB Output is correct
59 Correct 80 ms 35860 KB Output is correct
60 Correct 180 ms 46208 KB Output is correct
61 Correct 179 ms 45892 KB Output is correct
62 Correct 189 ms 47072 KB Output is correct
63 Correct 237 ms 50240 KB Output is correct
64 Correct 4 ms 29276 KB Output is correct
65 Correct 4 ms 29272 KB Output is correct
66 Correct 4 ms 29272 KB Output is correct
67 Correct 4 ms 29276 KB Output is correct
68 Correct 4 ms 29276 KB Output is correct
69 Correct 4 ms 29276 KB Output is correct
70 Correct 4 ms 29320 KB Output is correct
71 Correct 4 ms 29276 KB Output is correct
72 Correct 3 ms 29276 KB Output is correct
73 Correct 4 ms 29276 KB Output is correct
74 Correct 103 ms 53948 KB Output is correct
75 Correct 90 ms 43208 KB Output is correct
76 Correct 84 ms 43340 KB Output is correct
77 Correct 89 ms 46784 KB Output is correct
78 Correct 78 ms 57276 KB Output is correct
79 Correct 65 ms 50372 KB Output is correct
80 Correct 89 ms 50884 KB Output is correct
81 Correct 126 ms 54348 KB Output is correct
82 Correct 138 ms 56768 KB Output is correct
83 Correct 143 ms 60756 KB Output is correct
84 Correct 78 ms 46964 KB Output is correct
85 Correct 130 ms 57980 KB Output is correct
86 Correct 52 ms 38404 KB Output is correct
87 Correct 160 ms 47916 KB Output is correct
88 Correct 160 ms 47952 KB Output is correct
89 Correct 181 ms 50912 KB Output is correct
90 Correct 153 ms 62844 KB Output is correct
91 Correct 159 ms 59916 KB Output is correct
92 Correct 168 ms 55064 KB Output is correct
93 Correct 210 ms 58488 KB Output is correct
94 Correct 328 ms 60572 KB Output is correct
95 Correct 241 ms 64600 KB Output is correct
96 Correct 208 ms 51476 KB Output is correct
97 Correct 223 ms 56452 KB Output is correct