oj.uz

Submission #642553

# Submission time Handle Problem Language Result Execution time Memory
642553 2022-09-20T00:17:08 Z ymm Swapping Cities (APIO20_swap) C++17
0 / 100
 129 ms 30612 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200010;
const int lg = 18;
int par[N];
int sz[N];
int tim[N];
int lca[N][lg];
int lcaw[N][lg];
vector<int> A[N];

int root (int v) { return par[v] == -1? v: root(par[v]); }
void unite(int v, int u, int w)
{
	v = root(v);
	u = root(u);
	if (v == u) {
		tim[v] = min(tim[v], w);
		return;
	}
	if (sz[v] < sz[u])
		swap(v, u);
	par[u] = v;
	lcaw[u][0] = w;
	A[v].push_back(u);
	sz[v] += sz[u];
	if (tim[u] != N)
		tim[v] = min(tim[v], w);
}

void dfs(int v, int p, int w)
{
	w = tim[v] = min(tim[v], w);
	lca[v][0] = p;
	Loop (i,0,lg-1) {
		lca[v][i+1] = lca[lca[v][i]][i];
		lcaw[v][i+1] = max(lcaw[v][i], lcaw[lca[v][i]][i]);
	}
	for (int u : A[v])
		if (u != p)
			dfs(u, v, w);
}

void init(int n, int m,
          std::vector<int> u, std::vector<int> v, std::vector<int> w) {
	vector<pair<int,pii>> vec;
	Loop (i,0,m)
		vec.push_back({w[i],{v[i],u[i]}});
	fill(par, par+N, -1);
	fill(sz, sz+N, 1);
	fill(tim, tim+N, N);
	sort(vec.begin(), vec.end());
	for (auto dard : vec)
		unite(dard.second.first, dard.second.second, dard.first);
	int rt = 0;
	while (par[rt] != -1)
		++rt;
	dfs(rt, rt, N);
}

int getMinimumFuelCapacity(int x, int y) {
	int w = 0;
	LoopR (i,0,lg) {
		if (lca[x][i] != lca[y][i]) {
			w = max(w, lcaw[x][i]);
			w = max(w, lcaw[y][i]);
			x = lca[x][i];
			y = lca[y][i];
		}
	}
	w = max(w, lcaw[x][0]);
	w = max(w, lcaw[y][0]);
	x = lca[x][0];
	w = max(w, tim[x]);
	return w == N? -1: w;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7292 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Incorrect 4 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7292 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Incorrect 129 ms 30612 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7292 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Incorrect 4 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7292 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Incorrect 4 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7292 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Incorrect 4 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7292 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Incorrect 4 ms 7380 KB Output isn't correct
5 Halted 0 ms 0 KB -