oj.uz

Submission #764654

# Submission time Handle Problem Language Result Execution time Memory
764654 2023-06-23T18:03:41 Z raysh07 Swapping Cities (APIO20_swap) C++17
0 / 100
 6 ms 12756 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 15, M = 2e5 + 5, L = 21, INF = 2e9;
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]);
	}
}
 
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 LCA(int X, int Y) {
	for (int i = L - 1; i >= 0; i--) if (pr[Y][i] != pr[X][i]) Y = pr[Y][i], X = pr[X][i];
	return pr[X][0];
}
 
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])];
	int w = INF, lca = LCA(X, Y);
	for (int i = L - 1; i >= 0; i--) if (pr[Y][i] != pr[X][i] || D[pr[X][i]] <= 2) Y = pr[Y][i], X = pr[X][i];
	smin(w, (D[pr[X][0]] > 2 ? Wtmp[pr[X][0] - M] : INF));
	if (h[X] <= h[lca]) smin(w, max(Wtmp[X - M], ext[X]));
	return w >= INF ? -1 : w;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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