oj.uz

Submission #642554

# Submission time Handle Problem Language Result Execution time Memory
642554 2022-09-20T00:30:04 Z ymm Swapping Cities (APIO20_swap) C++17
6 / 100
 166 ms 32732 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 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] != inf)
		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, inf);
	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, inf);
}

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 == inf? -1: w;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7456 KB Output is correct
6 Correct 4 ms 7460 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 4 ms 7456 KB Output is correct
9 Correct 61 ms 23832 KB Output is correct
10 Correct 77 ms 27488 KB Output is correct
11 Correct 74 ms 27224 KB Output is correct
12 Correct 80 ms 28372 KB Output is correct
13 Correct 67 ms 27912 KB Output is correct
14 Correct 69 ms 24124 KB Output is correct
15 Correct 149 ms 31620 KB Output is correct
16 Correct 149 ms 30968 KB Output is correct
17 Correct 150 ms 32308 KB Output is correct
18 Correct 135 ms 31544 KB Output is correct
19 Correct 63 ms 15576 KB Output is correct
20 Correct 166 ms 31716 KB Output is correct
21 Correct 149 ms 31528 KB Output is correct
22 Correct 151 ms 32732 KB Output is correct
23 Correct 136 ms 32012 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Incorrect 132 ms 26492 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 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7456 KB Output is correct
6 Correct 4 ms 7460 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 4 ms 7456 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Incorrect 4 ms 7524 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7456 KB Output is correct
7 Correct 4 ms 7460 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 4 ms 7456 KB Output is correct
10 Correct 61 ms 23832 KB Output is correct
11 Correct 77 ms 27488 KB Output is correct
12 Correct 74 ms 27224 KB Output is correct
13 Correct 80 ms 28372 KB Output is correct
14 Correct 67 ms 27912 KB Output is correct
15 Incorrect 4 ms 7524 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7456 KB Output is correct
6 Correct 4 ms 7460 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 4 ms 7456 KB Output is correct
9 Correct 61 ms 23832 KB Output is correct
10 Correct 77 ms 27488 KB Output is correct
11 Correct 74 ms 27224 KB Output is correct
12 Correct 80 ms 28372 KB Output is correct
13 Correct 67 ms 27912 KB Output is correct
14 Correct 69 ms 24124 KB Output is correct
15 Correct 149 ms 31620 KB Output is correct
16 Correct 149 ms 30968 KB Output is correct
17 Correct 150 ms 32308 KB Output is correct
18 Correct 135 ms 31544 KB Output is correct
19 Incorrect 132 ms 26492 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7456 KB Output is correct
7 Correct 4 ms 7460 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 4 ms 7456 KB Output is correct
10 Correct 61 ms 23832 KB Output is correct
11 Correct 77 ms 27488 KB Output is correct
12 Correct 74 ms 27224 KB Output is correct
13 Correct 80 ms 28372 KB Output is correct
14 Correct 67 ms 27912 KB Output is correct
15 Correct 69 ms 24124 KB Output is correct
16 Correct 149 ms 31620 KB Output is correct
17 Correct 149 ms 30968 KB Output is correct
18 Correct 150 ms 32308 KB Output is correct
19 Correct 135 ms 31544 KB Output is correct
20 Incorrect 132 ms 26492 KB Output isn't correct
21 Halted 0 ms 0 KB -