oj.uz

Submission #743639

# Submission time Handle Problem Language Result Execution time Memory
743639 2023-05-17T15:01:59 Z RushB Swapping Cities (APIO20_swap) C++17
0 / 100
 236 ms 45216 KB 
//happier ending for folks like us? 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 15, M = 2e5 + 5, L = 21, INF = 0x3f3f3f3f;
int p[N], dpr[N], pr[N][L], ext[N], P[N], h[N], rt, D[N], deg[N];
vector<int> adj[N], Wtmp;
inline 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]);
	}
}
int gpr(int u) {return dpr[u] == u ? u : dpr[u] = gpr(dpr[u]);}
bool merge(int u, int v, int id) {
	int tu = u, tv = v;
	deg[tu]++, deg[tv]++;
	u = gpr(u), v = gpr(v);
	if (u == v) return false;
	dpr[u] = dpr[v] = id + M;
	D[id + M] = max({D[u], D[v], deg[tu], deg[tv]});
	adj[id + M].push_back(u);
	adj[id + M].push_back(v);
	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, 0x3f, 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]);
		}
	}
	rt = gpr(0), pr[rt][0] = rt, dfs(rt);
}
int getMinimumFuelCapacity(int X, int Y) {
	return -1;
	if (h[X] < h[Y]) swap(X, Y);
	while (h[Y] < h[X]) X = pr[X][__lg(h[X] - h[Y])];
	for (int i = L - 1; i >= 0; i--) if (pr[Y][i] != pr[X][i]) 
		Y = pr[Y][i], X = pr[X][i];
	int lca = pr[X][0], w = Wtmp[lca - M];
	if (D[lca] > 2) return w;
	if (lca == pr[lca][0]) return -1;
	w = max(w, min(ext[lca], Wtmp[pr[lca][0] - M]));
	return w >= INF ? -1 : w;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12852 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 13060 KB Output is correct
6 Correct 9 ms 13040 KB Output is correct
7 Correct 9 ms 13044 KB Output is correct
8 Correct 8 ms 13140 KB Output is correct
9 Correct 102 ms 32064 KB Output is correct
10 Correct 139 ms 36428 KB Output is correct
11 Correct 140 ms 36036 KB Output is correct
12 Correct 139 ms 37384 KB Output is correct
13 Correct 169 ms 41216 KB Output is correct
14 Correct 135 ms 32164 KB Output is correct
15 Correct 184 ms 38488 KB Output is correct
16 Correct 181 ms 37872 KB Output is correct
17 Correct 199 ms 39200 KB Output is correct
18 Correct 236 ms 43164 KB Output is correct
19 Incorrect 63 ms 19276 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12852 KB Output is correct
3 Incorrect 207 ms 45216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12852 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 13060 KB Output is correct
6 Correct 9 ms 13040 KB Output is correct
7 Correct 9 ms 13044 KB Output is correct
8 Correct 8 ms 13140 KB Output is correct
9 Incorrect 7 ms 12884 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12852 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 13060 KB Output is correct
6 Correct 9 ms 13040 KB Output is correct
7 Correct 9 ms 13044 KB Output is correct
8 Correct 8 ms 13140 KB Output is correct
9 Correct 102 ms 32064 KB Output is correct
10 Correct 139 ms 36428 KB Output is correct
11 Correct 140 ms 36036 KB Output is correct
12 Correct 139 ms 37384 KB Output is correct
13 Correct 169 ms 41216 KB Output is correct
14 Correct 135 ms 32164 KB Output is correct
15 Correct 184 ms 38488 KB Output is correct
16 Correct 181 ms 37872 KB Output is correct
17 Correct 199 ms 39200 KB Output is correct
18 Correct 236 ms 43164 KB Output is correct
19 Incorrect 207 ms 45216 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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