oj.uz

Submission #743587

# Submission time Handle Problem Language Result Execution time Memory
743587 2023-05-17T14:12:55 Z RushB Swapping Cities (APIO20_swap) C++17
0 / 100
 468 ms 49040 KB 
#include "swap.h"
//:| OK. 
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 15;
const int M = 2e5 + 5;
const int L = 21;
int p[N], dpr[N], pr[N][L], ext[N], P[N], h[N];
vector<int> adj[N], Wtmp;

void smin(int &a, int b) {a = min(a, b);}

void dfs(int v) {
	for (int i = 1; i < L; i++) pr[v][i] = pr[pr[v][i - 1]][i - 1];
	for (auto u: adj[v]) {
		pr[u][0] = v;
		h[u] = h[v] + 1;
		dfs(u);
		smin(ext[v], ext[u]);
		P[v] = max(P[v], P[u]);
	}
	P[v] = max(P[v], (int) adj[v].size() - (pr[v][0] == v));
}
void add_edge(int u, int e) {
	adj[e].push_back(u);
}

int gpr(int u) {
	return dpr[u] == u ? u : dpr[u] = gpr(dpr[u]);
}

bool merge(int u, int v, int id) {
	u = gpr(u), v = gpr(v);
	if (u == v) return false;
	dpr[u] = id + M;
	dpr[v] = id + M;
	add_edge(u, id + M);
	add_edge(v, id + M);
	return true;
}

void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	iota(p, p + m, 0);
	sort(p, p + m, [&](const int x, const int y) {return W[x] < W[y];});
	iota(dpr, dpr + N, 0);

	memset(ext, 0x3f3f3f, sizeof ext);
	Wtmp = W;
	
	for (int i = 0; i < m; i++) {
		const int id = p[i];
		if (!merge(U[id], V[id], id)) {
			smin(ext[U[id]], W[id]);
			smin(ext[V[id]], W[id]);
		}
	}
	int rt = gpr(0);
	pr[rt][0] = rt;
	dfs(rt);
}

int getMinimumFuelCapacity(int X, int Y) {
	if (h[X] < h[Y]) swap(X, Y);
	while (h[Y] < h[X]) X = pr[X][__lg(h[X] - h[Y])];
	assert(Y != X);
	for (int i = L - 1; i >= 0; i--) if (pr[Y][i] != pr[X][i]) 
		Y = pr[Y][i], X = pr[X][i];
	assert(pr[X][0] == pr[Y][0]);
	int lca = pr[X][0], l = lca - M, w = Wtmp[l];
	if (P[lca] > 2) return w;
	w = max(w, ext[lca]);
	return w > M ? -1 : w;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 6 ms 12776 KB Output is correct
4 Correct 7 ms 12912 KB Output is correct
5 Correct 8 ms 13036 KB Output is correct
6 Correct 9 ms 13012 KB Output is correct
7 Correct 8 ms 13044 KB Output is correct
8 Correct 10 ms 13172 KB Output is correct
9 Correct 119 ms 33572 KB Output is correct
10 Correct 138 ms 38076 KB Output is correct
11 Correct 132 ms 37708 KB Output is correct
12 Correct 144 ms 39148 KB Output is correct
13 Correct 181 ms 43896 KB Output is correct
14 Correct 128 ms 33868 KB Output is correct
15 Correct 293 ms 40748 KB Output is correct
16 Correct 276 ms 40112 KB Output is correct
17 Correct 301 ms 41484 KB Output is correct
18 Correct 468 ms 46292 KB Output is correct
19 Incorrect 89 ms 20940 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Incorrect 435 ms 49040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 6 ms 12776 KB Output is correct
4 Correct 7 ms 12912 KB Output is correct
5 Correct 8 ms 13036 KB Output is correct
6 Correct 9 ms 13012 KB Output is correct
7 Correct 8 ms 13044 KB Output is correct
8 Correct 10 ms 13172 KB Output is correct
9 Correct 8 ms 12756 KB Output is correct
10 Incorrect 9 ms 13140 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 9 ms 12880 KB Output is correct
3 Correct 8 ms 12884 KB Output is correct
4 Correct 6 ms 12776 KB Output is correct
5 Correct 7 ms 12912 KB Output is correct
6 Correct 8 ms 13036 KB Output is correct
7 Correct 9 ms 13012 KB Output is correct
8 Correct 8 ms 13044 KB Output is correct
9 Correct 10 ms 13172 KB Output is correct
10 Correct 119 ms 33572 KB Output is correct
11 Correct 138 ms 38076 KB Output is correct
12 Correct 132 ms 37708 KB Output is correct
13 Correct 144 ms 39148 KB Output is correct
14 Correct 181 ms 43896 KB Output is correct
15 Incorrect 9 ms 13140 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12880 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 6 ms 12776 KB Output is correct
4 Correct 7 ms 12912 KB Output is correct
5 Correct 8 ms 13036 KB Output is correct
6 Correct 9 ms 13012 KB Output is correct
7 Correct 8 ms 13044 KB Output is correct
8 Correct 10 ms 13172 KB Output is correct
9 Correct 119 ms 33572 KB Output is correct
10 Correct 138 ms 38076 KB Output is correct
11 Correct 132 ms 37708 KB Output is correct
12 Correct 144 ms 39148 KB Output is correct
13 Correct 181 ms 43896 KB Output is correct
14 Correct 128 ms 33868 KB Output is correct
15 Correct 293 ms 40748 KB Output is correct
16 Correct 276 ms 40112 KB Output is correct
17 Correct 301 ms 41484 KB Output is correct
18 Correct 468 ms 46292 KB Output is correct
19 Incorrect 435 ms 49040 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 9 ms 12880 KB Output is correct
3 Correct 8 ms 12884 KB Output is correct
4 Correct 6 ms 12776 KB Output is correct
5 Correct 7 ms 12912 KB Output is correct
6 Correct 8 ms 13036 KB Output is correct
7 Correct 9 ms 13012 KB Output is correct
8 Correct 8 ms 13044 KB Output is correct
9 Correct 10 ms 13172 KB Output is correct
10 Correct 119 ms 33572 KB Output is correct
11 Correct 138 ms 38076 KB Output is correct
12 Correct 132 ms 37708 KB Output is correct
13 Correct 144 ms 39148 KB Output is correct
14 Correct 181 ms 43896 KB Output is correct
15 Correct 128 ms 33868 KB Output is correct
16 Correct 293 ms 40748 KB Output is correct
17 Correct 276 ms 40112 KB Output is correct
18 Correct 301 ms 41484 KB Output is correct
19 Correct 468 ms 46292 KB Output is correct
20 Incorrect 435 ms 49040 KB Output isn't correct
21 Halted 0 ms 0 KB -