Submission #743606

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743606	2023-05-17T14:24:52 Z	RushB	Swapping Cities (APIO20_swap)	C++17	0 / 100	397 ms	48460 KB

swap

//happier ending for folks like us? 
#include "swap.h"
#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], rt, D[N], deg[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());
}
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) {
	int tu = u, tv = v;
	deg[tu]++, deg[tv]++;
	u = gpr(u), v = gpr(v);
	if (u == v) return false;
	dpr[u] = id + M;
	dpr[v] = id + M;
	D[id + M] = max({D[u], D[v], deg[tu], deg[tv]});
	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]);
		}
	}
	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], p = P[lca];

	if (D[lca] > 2) return w;
	w = max(w, ext[lca]);
	return w > M ? -1 : w;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:72:48: warning: unused variable 'p' [-Wunused-variable]
   72 |  int lca = pr[X][0], l = lca - M, w = Wtmp[l], p = P[lca];
      |                                                ^

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12884 KB	Output is correct
2	Correct	6 ms	12856 KB	Output is correct
3	Correct	7 ms	12792 KB	Output is correct
4	Correct	8 ms	12972 KB	Output is correct
5	Correct	8 ms	13116 KB	Output is correct
6	Correct	8 ms	13036 KB	Output is correct
7	Correct	7 ms	13056 KB	Output is correct
8	Correct	8 ms	13172 KB	Output is correct
9	Correct	101 ms	32476 KB	Output is correct
10	Correct	129 ms	36812 KB	Output is correct
11	Correct	124 ms	36532 KB	Output is correct
12	Correct	135 ms	38024 KB	Output is correct
13	Correct	167 ms	42696 KB	Output is correct
14	Correct	113 ms	32512 KB	Output is correct
15	Correct	250 ms	38908 KB	Output is correct
16	Correct	226 ms	38260 KB	Output is correct
17	Correct	244 ms	39732 KB	Output is correct
18	Correct	382 ms	44308 KB	Output is correct
19	Incorrect	82 ms	19080 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	12884 KB	Output is correct
2	Correct	6 ms	12856 KB	Output is correct
3	Incorrect	397 ms	48460 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	12884 KB	Output is correct
2	Correct	6 ms	12856 KB	Output is correct
3	Correct	7 ms	12792 KB	Output is correct
4	Correct	8 ms	12972 KB	Output is correct
5	Correct	8 ms	13116 KB	Output is correct
6	Correct	8 ms	13036 KB	Output is correct
7	Correct	7 ms	13056 KB	Output is correct
8	Correct	8 ms	13172 KB	Output is correct
9	Correct	7 ms	12884 KB	Output is correct
10	Correct	8 ms	13100 KB	Output is correct
11	Correct	8 ms	13040 KB	Output is correct
12	Correct	8 ms	13040 KB	Output is correct
13	Correct	8 ms	13012 KB	Output is correct
14	Correct	8 ms	13012 KB	Output is correct
15	Incorrect	8 ms	13140 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12884 KB	Output is correct
2	Correct	7 ms	12884 KB	Output is correct
3	Correct	6 ms	12856 KB	Output is correct
4	Correct	7 ms	12792 KB	Output is correct
5	Correct	8 ms	12972 KB	Output is correct
6	Correct	8 ms	13116 KB	Output is correct
7	Correct	8 ms	13036 KB	Output is correct
8	Correct	7 ms	13056 KB	Output is correct
9	Correct	8 ms	13172 KB	Output is correct
10	Correct	101 ms	32476 KB	Output is correct
11	Correct	129 ms	36812 KB	Output is correct
12	Correct	124 ms	36532 KB	Output is correct
13	Correct	135 ms	38024 KB	Output is correct
14	Correct	167 ms	42696 KB	Output is correct
15	Correct	8 ms	13100 KB	Output is correct
16	Correct	8 ms	13040 KB	Output is correct
17	Correct	8 ms	13040 KB	Output is correct
18	Correct	8 ms	13012 KB	Output is correct
19	Correct	8 ms	13012 KB	Output is correct
20	Incorrect	8 ms	13140 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	12884 KB	Output is correct
2	Correct	6 ms	12856 KB	Output is correct
3	Correct	7 ms	12792 KB	Output is correct
4	Correct	8 ms	12972 KB	Output is correct
5	Correct	8 ms	13116 KB	Output is correct
6	Correct	8 ms	13036 KB	Output is correct
7	Correct	7 ms	13056 KB	Output is correct
8	Correct	8 ms	13172 KB	Output is correct
9	Correct	101 ms	32476 KB	Output is correct
10	Correct	129 ms	36812 KB	Output is correct
11	Correct	124 ms	36532 KB	Output is correct
12	Correct	135 ms	38024 KB	Output is correct
13	Correct	167 ms	42696 KB	Output is correct
14	Correct	113 ms	32512 KB	Output is correct
15	Correct	250 ms	38908 KB	Output is correct
16	Correct	226 ms	38260 KB	Output is correct
17	Correct	244 ms	39732 KB	Output is correct
18	Correct	382 ms	44308 KB	Output is correct
19	Incorrect	397 ms	48460 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12884 KB	Output is correct
2	Correct	7 ms	12884 KB	Output is correct
3	Correct	6 ms	12856 KB	Output is correct
4	Correct	7 ms	12792 KB	Output is correct
5	Correct	8 ms	12972 KB	Output is correct
6	Correct	8 ms	13116 KB	Output is correct
7	Correct	8 ms	13036 KB	Output is correct
8	Correct	7 ms	13056 KB	Output is correct
9	Correct	8 ms	13172 KB	Output is correct
10	Correct	101 ms	32476 KB	Output is correct
11	Correct	129 ms	36812 KB	Output is correct
12	Correct	124 ms	36532 KB	Output is correct
13	Correct	135 ms	38024 KB	Output is correct
14	Correct	167 ms	42696 KB	Output is correct
15	Correct	113 ms	32512 KB	Output is correct
16	Correct	250 ms	38908 KB	Output is correct
17	Correct	226 ms	38260 KB	Output is correct
18	Correct	244 ms	39732 KB	Output is correct
19	Correct	382 ms	44308 KB	Output is correct
20	Incorrect	397 ms	48460 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #743606

Compilation message

Subtask #1 0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0