oj.uz

Submission #642556

# Submission time Handle Problem Language Result Execution time Memory
642556 2022-09-20T00:56:27 Z ymm Swapping Cities (APIO20_swap) C++17
0 / 100
 97 ms 13932 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 inf = 2e9;
const int lg = 18;
int par[N];
int parw[N];
int sz[N];
int tim[N];
bool pleaf[N];
bool proot[N];
vector<int> A[N];

int root (int v) { return par[v] == -1? v: root(par[v]); }
void unite(int v, int u, int w)
{
	int v0 = v, u0 = u;
	v = root(v);
	u = root(u);
	if (v == u) {
		proot[v] = false;
		tim[v] = min(tim[v], w);
		return;
	}
	if (sz[v] < sz[u])
		swap(v, u);
	par[u] = v;
	parw[u] = w;
	A[v].push_back(u);
	sz[v] += sz[u];
	if (!proot[v] || !proot[u] || !pleaf[v0] || !pleaf[u0]) {
		proot[v] = false;
		tim[v] = min(tim[v], w);
	}
	if (sz[v] - sz[u] != 1)
		pleaf[v0] = false;
	if (sz[u] != 1)
		pleaf[u0] = false;
}

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, inf);
	fill(proot, proot+N, true);
	fill(pleaf, pleaf+N, true);
	sort(vec.begin(), vec.end());
	for (auto dard : vec)
		unite(dard.second.first, dard.second.second, dard.first);
}

int height(int v)
{
	int ans = 0;
	while (par[v] != -1) {
		++ans;
		v = par[v];
	}
	return ans;
}

int getMinimumFuelCapacity(int x, int y) {
	int diff = height(y) - height(x);
	int w = 0;
	while (diff > 0) {
		w = max(w, parw[y]);
		y = par[y];
		--diff;
	}
	while (diff < 0) {
		w = max(w, parw[x]);
		x = par[x];
		++diff;
	}
	while (x != y) {
		w = max(w, parw[x]);
		w = max(w, parw[y]);
		x = par[x];
		y = par[y];
	}
	int t = tim[x];
	while (par[x] != -1) {
		t = min(t, max(parw[x], tim[par[x]]));
		x = par[x];
	}
	w = max(w, t);
	return w == inf? -1: w;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7636 KB Output is correct
2 Correct 4 ms 7636 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Incorrect 4 ms 7764 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 7636 KB Output is correct
2 Correct 4 ms 7636 KB Output is correct
3 Incorrect 97 ms 13932 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 7636 KB Output is correct
2 Correct 4 ms 7636 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Incorrect 4 ms 7764 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 7636 KB Output is correct
2 Correct 4 ms 7636 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Incorrect 4 ms 7764 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 7636 KB Output is correct
2 Correct 4 ms 7636 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Incorrect 4 ms 7764 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 7636 KB Output is correct
2 Correct 4 ms 7636 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Incorrect 4 ms 7764 KB Output isn't correct
5 Halted 0 ms 0 KB -