oj.uz

Submission #562247

# Submission time Handle Problem Language Result Execution time Memory
562247 2022-05-14T08:03:12 Z hollwo_pelw Swapping Cities (APIO20_swap) C++17
6 / 100
 343 ms 43084 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 2e5 + 5;

int n, m, fa[N + M], val[N + M], col[N + M];
int par[19][N + M], nxt[N + M], d[N + M];
vector<int> adj[N + M];

inline int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }
inline void merge(int u, int v, int w) {
	if ((u = find(u)) == (v = find(v))) {
		if (!col[u]) {
			fa[u] = ++ n;
			adj[n].push_back(u);
			col[n] = 1, val[n] = w;
		}
		return ;
	}
	fa[u] = fa[v] = ++ n;
	adj[n].push_back(u);
	adj[n].push_back(v);
	col[n] = col[u] | col[v], val[n] = w;
}

void pre_dfs(int u, int f = 0) {
	if (col[u]) f = u;
	nxt[u] = f;

	for (int v : adj[u]) {

		d[v] = d[par[0][v] = u] + 1;
		for (int i = 1; i < 19; i++)
			par[i][v] = par[i - 1][par[i - 1][v]];

		pre_dfs(v, f);
	}
}

inline int lca(int u, int v) {
	if (d[u] > d[v]) swap(u, v);
	
	for (int i = 19; i --; )
		if ((d[v] - d[u]) >> i & 1)
			v = par[i][v];
	if (u == v) return u;
	
	for (int i = 19; i --; )
		if (par[i][u] != par[i][v]) {
			u = par[i][u];
			v = par[i][v];
		}
	return par[0][u];
}

void init(int _n, int _m, vector<int> U, vector<int> V, vector<int> W) {
	n = _n, m = _m;

	iota(fa, fa + N + M, 0);

	vector<int> ids(m);
	iota(ids.begin(), ids.end(), 0);
	sort(ids.begin(), ids.end(), [&](const int &i, const int &j){
		return W[i] < W[j];
	});

	for (int i : ids)
		merge(U[i] + 1, V[i] + 1, W[i]);

	val[0] = -1, pre_dfs(n);
}

int getMinimumFuelCapacity(int X, int Y) {
	return val[nxt[lca(X + 1, Y + 1)]];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Correct 5 ms 8660 KB Output is correct
4 Correct 6 ms 8660 KB Output is correct
5 Correct 7 ms 8776 KB Output is correct
6 Correct 7 ms 8776 KB Output is correct
7 Correct 6 ms 8912 KB Output is correct
8 Correct 6 ms 8912 KB Output is correct
9 Correct 97 ms 28356 KB Output is correct
10 Correct 130 ms 32836 KB Output is correct
11 Correct 126 ms 32456 KB Output is correct
12 Correct 146 ms 33988 KB Output is correct
13 Correct 102 ms 37768 KB Output is correct
14 Correct 110 ms 28712 KB Output is correct
15 Correct 275 ms 36780 KB Output is correct
16 Correct 257 ms 36280 KB Output is correct
17 Correct 296 ms 37696 KB Output is correct
18 Correct 343 ms 41572 KB Output is correct
19 Correct 87 ms 17628 KB Output is correct
20 Correct 262 ms 37768 KB Output is correct
21 Correct 273 ms 37276 KB Output is correct
22 Correct 305 ms 38932 KB Output is correct
23 Correct 338 ms 42816 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Incorrect 318 ms 43084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Correct 5 ms 8660 KB Output is correct
4 Correct 6 ms 8660 KB Output is correct
5 Correct 7 ms 8776 KB Output is correct
6 Correct 7 ms 8776 KB Output is correct
7 Correct 6 ms 8912 KB Output is correct
8 Correct 6 ms 8912 KB Output is correct
9 Correct 5 ms 8660 KB Output is correct
10 Incorrect 7 ms 8916 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Correct 5 ms 8660 KB Output is correct
4 Correct 5 ms 8660 KB Output is correct
5 Correct 6 ms 8660 KB Output is correct
6 Correct 7 ms 8776 KB Output is correct
7 Correct 7 ms 8776 KB Output is correct
8 Correct 6 ms 8912 KB Output is correct
9 Correct 6 ms 8912 KB Output is correct
10 Correct 97 ms 28356 KB Output is correct
11 Correct 130 ms 32836 KB Output is correct
12 Correct 126 ms 32456 KB Output is correct
13 Correct 146 ms 33988 KB Output is correct
14 Correct 102 ms 37768 KB Output is correct
15 Incorrect 7 ms 8916 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Correct 5 ms 8660 KB Output is correct
4 Correct 6 ms 8660 KB Output is correct
5 Correct 7 ms 8776 KB Output is correct
6 Correct 7 ms 8776 KB Output is correct
7 Correct 6 ms 8912 KB Output is correct
8 Correct 6 ms 8912 KB Output is correct
9 Correct 97 ms 28356 KB Output is correct
10 Correct 130 ms 32836 KB Output is correct
11 Correct 126 ms 32456 KB Output is correct
12 Correct 146 ms 33988 KB Output is correct
13 Correct 102 ms 37768 KB Output is correct
14 Correct 110 ms 28712 KB Output is correct
15 Correct 275 ms 36780 KB Output is correct
16 Correct 257 ms 36280 KB Output is correct
17 Correct 296 ms 37696 KB Output is correct
18 Correct 343 ms 41572 KB Output is correct
19 Incorrect 318 ms 43084 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Correct 5 ms 8660 KB Output is correct
4 Correct 5 ms 8660 KB Output is correct
5 Correct 6 ms 8660 KB Output is correct
6 Correct 7 ms 8776 KB Output is correct
7 Correct 7 ms 8776 KB Output is correct
8 Correct 6 ms 8912 KB Output is correct
9 Correct 6 ms 8912 KB Output is correct
10 Correct 97 ms 28356 KB Output is correct
11 Correct 130 ms 32836 KB Output is correct
12 Correct 126 ms 32456 KB Output is correct
13 Correct 146 ms 33988 KB Output is correct
14 Correct 102 ms 37768 KB Output is correct
15 Correct 110 ms 28712 KB Output is correct
16 Correct 275 ms 36780 KB Output is correct
17 Correct 257 ms 36280 KB Output is correct
18 Correct 296 ms 37696 KB Output is correct
19 Correct 343 ms 41572 KB Output is correct
20 Incorrect 318 ms 43084 KB Output isn't correct
21 Halted 0 ms 0 KB -