Submission #743622

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743622	2023-05-17T14:47:49 Z	RushB	Swapping Cities (APIO20_swap)	C++17	0 / 100	393 ms	46748 KB

swap

//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);
	for (int i = 0; i < n; i++) if (i != rt) smin(ext[i], W[pr[i][0] - M]);
}
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])];
	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;
	w = max(w, ext[lca]);
	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	12756 KB	Output is correct
3	Correct	7 ms	12776 KB	Output is correct
4	Correct	7 ms	12884 KB	Output is correct
5	Correct	9 ms	13040 KB	Output is correct
6	Correct	9 ms	13044 KB	Output is correct
7	Correct	9 ms	13044 KB	Output is correct
8	Correct	9 ms	13168 KB	Output is correct
9	Correct	116 ms	32124 KB	Output is correct
10	Correct	128 ms	36420 KB	Output is correct
11	Correct	129 ms	36044 KB	Output is correct
12	Correct	148 ms	37264 KB	Output is correct
13	Correct	160 ms	41284 KB	Output is correct
14	Correct	120 ms	32180 KB	Output is correct
15	Correct	245 ms	38572 KB	Output is correct
16	Correct	234 ms	37996 KB	Output is correct
17	Correct	233 ms	39328 KB	Output is correct
18	Correct	393 ms	43252 KB	Output is correct
19	Incorrect	93 ms	19596 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	12756 KB	Output is correct
3	Incorrect	363 ms	46748 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	12756 KB	Output is correct
3	Correct	7 ms	12776 KB	Output is correct
4	Correct	7 ms	12884 KB	Output is correct
5	Correct	9 ms	13040 KB	Output is correct
6	Correct	9 ms	13044 KB	Output is correct
7	Correct	9 ms	13044 KB	Output is correct
8	Correct	9 ms	13168 KB	Output is correct
9	Correct	8 ms	12764 KB	Output is correct
10	Correct	8 ms	13044 KB	Output is correct
11	Correct	8 ms	13048 KB	Output is correct
12	Correct	8 ms	13012 KB	Output is correct
13	Correct	8 ms	13012 KB	Output is correct
14	Correct	8 ms	13092 KB	Output is correct
15	Incorrect	9 ms	13012 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	12764 KB	Output is correct
2	Correct	7 ms	12756 KB	Output is correct
3	Correct	7 ms	12756 KB	Output is correct
4	Correct	7 ms	12776 KB	Output is correct
5	Correct	7 ms	12884 KB	Output is correct
6	Correct	9 ms	13040 KB	Output is correct
7	Correct	9 ms	13044 KB	Output is correct
8	Correct	9 ms	13044 KB	Output is correct
9	Correct	9 ms	13168 KB	Output is correct
10	Correct	116 ms	32124 KB	Output is correct
11	Correct	128 ms	36420 KB	Output is correct
12	Correct	129 ms	36044 KB	Output is correct
13	Correct	148 ms	37264 KB	Output is correct
14	Correct	160 ms	41284 KB	Output is correct
15	Correct	8 ms	13044 KB	Output is correct
16	Correct	8 ms	13048 KB	Output is correct
17	Correct	8 ms	13012 KB	Output is correct
18	Correct	8 ms	13012 KB	Output is correct
19	Correct	8 ms	13092 KB	Output is correct
20	Incorrect	9 ms	13012 KB	Output isn't correct
21	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	12756 KB	Output is correct
3	Correct	7 ms	12776 KB	Output is correct
4	Correct	7 ms	12884 KB	Output is correct
5	Correct	9 ms	13040 KB	Output is correct
6	Correct	9 ms	13044 KB	Output is correct
7	Correct	9 ms	13044 KB	Output is correct
8	Correct	9 ms	13168 KB	Output is correct
9	Correct	116 ms	32124 KB	Output is correct
10	Correct	128 ms	36420 KB	Output is correct
11	Correct	129 ms	36044 KB	Output is correct
12	Correct	148 ms	37264 KB	Output is correct
13	Correct	160 ms	41284 KB	Output is correct
14	Correct	120 ms	32180 KB	Output is correct
15	Correct	245 ms	38572 KB	Output is correct
16	Correct	234 ms	37996 KB	Output is correct
17	Correct	233 ms	39328 KB	Output is correct
18	Correct	393 ms	43252 KB	Output is correct
19	Incorrect	363 ms	46748 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	12764 KB	Output is correct
2	Correct	7 ms	12756 KB	Output is correct
3	Correct	7 ms	12756 KB	Output is correct
4	Correct	7 ms	12776 KB	Output is correct
5	Correct	7 ms	12884 KB	Output is correct
6	Correct	9 ms	13040 KB	Output is correct
7	Correct	9 ms	13044 KB	Output is correct
8	Correct	9 ms	13044 KB	Output is correct
9	Correct	9 ms	13168 KB	Output is correct
10	Correct	116 ms	32124 KB	Output is correct
11	Correct	128 ms	36420 KB	Output is correct
12	Correct	129 ms	36044 KB	Output is correct
13	Correct	148 ms	37264 KB	Output is correct
14	Correct	160 ms	41284 KB	Output is correct
15	Correct	120 ms	32180 KB	Output is correct
16	Correct	245 ms	38572 KB	Output is correct
17	Correct	234 ms	37996 KB	Output is correct
18	Correct	233 ms	39328 KB	Output is correct
19	Correct	393 ms	43252 KB	Output is correct
20	Incorrect	363 ms	46748 KB	Output isn't correct
21	Halted	0 ms	0 KB	-