oj.uz

Submission #562249

# Submission time Handle Problem Language Result Execution time Memory
562249 2022-05-14T08:08:37 Z hollwo_pelw Swapping Cities (APIO20_swap) C++17
0 / 100
 187 ms 39316 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 -1;
	return val[nxt[lca(X + 1, Y + 1)]];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Correct 5 ms 8604 KB Output is correct
4 Correct 5 ms 8660 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 6 ms 8788 KB Output is correct
7 Correct 6 ms 8900 KB Output is correct
8 Correct 7 ms 8916 KB Output is correct
9 Correct 95 ms 26788 KB Output is correct
10 Correct 140 ms 30796 KB Output is correct
11 Correct 117 ms 30460 KB Output is correct
12 Correct 121 ms 31628 KB Output is correct
13 Correct 104 ms 35724 KB Output is correct
14 Correct 127 ms 26964 KB Output is correct
15 Correct 187 ms 32516 KB Output is correct
16 Correct 167 ms 31888 KB Output is correct
17 Correct 175 ms 33316 KB Output is correct
18 Correct 161 ms 37228 KB Output is correct
19 Incorrect 55 ms 14568 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8660 KB Output is correct
2 Correct 5 ms 8660 KB Output is correct
3 Correct 5 ms 8604 KB Output is correct
4 Correct 5 ms 8660 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 6 ms 8788 KB Output is correct
7 Correct 6 ms 8900 KB Output is correct
8 Correct 7 ms 8916 KB Output is correct
9 Correct 95 ms 26788 KB Output is correct
10 Correct 140 ms 30796 KB Output is correct
11 Correct 117 ms 30460 KB Output is correct
12 Correct 121 ms 31628 KB Output is correct
13 Correct 104 ms 35724 KB Output is correct
14 Correct 127 ms 26964 KB Output is correct
15 Correct 187 ms 32516 KB Output is correct
16 Correct 167 ms 31888 KB Output is correct
17 Correct 175 ms 33316 KB Output is correct
18 Correct 161 ms 37228 KB Output is correct
19 Incorrect 130 ms 39316 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8660 KB Output isn't correct
2 Halted 0 ms 0 KB -