oj.uz

Submission #499295

# Submission time Handle Problem Language Result Execution time Memory
499295 2021-12-27T20:56:19 Z sidon Swapping Cities (APIO20_swap) C++17
6 / 100
 426 ms 54296 KB 
#include <bits/stdc++.h>
using namespace std;
#include "swap.h"

const int Z = 1e5, B = 18, INF = 2e9;

array<int, B> p[Z], q[Z], r[Z];
vector<int> e(Z, -1), d(Z);
vector<array<int, 2>> g[Z];
set<array<int, 2>> s[Z];

int find(int u) {
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

void dfs_0(int u) {
	for(auto &[v, w] : g[u]) if(v != p[u][0]) {
		p[v][0] = u, q[v][0] = w, d[v] = d[u] + 1;
		dfs_0(v);

		if(size(s[u]) < size(s[v]))
			s[u].swap(s[v]);

		for(auto &i : s[v])
			if(s[u].find(i) == end(s[u]))
				s[u].insert(i);
			else
				s[u].erase(i);
	}
	if(!empty(s[u])) r[u][0] = (*begin(s[u]))[0];
	else r[u][0] = INF;
}

void dfs_1(int u) {
	for(int i = 1; i < B; i++) {
		p[u][i] = p[p[u][i-1]][i-1];
		q[u][i] = max(q[u][i-1], q[p[u][i-1]][i-1]);
		r[u][i] = min(r[u][i-1], r[p[u][i-1]][i-1]);
	}
	for(auto &[v, w] : g[u]) if(v != p[u][0])
		dfs_1(v);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	array<int, 3> h[M];
	for(int i = 0; i < M; i++) {
		h[i] = {W[i], U[i], V[i]};
	}
	sort(h, h+M);
	for(int i = 0; i < M; i++) {
		int u = find(h[i][1]), v = find(h[i][2]), w = h[i][0];
		if(u == v)
			for(int k : {1, 2})
				s[h[i][k]].insert({w, i});
		else {
			if(e[u] > e[v]) swap(u, v);
			e[u] += e[v], e[v] = u;
			for(int k : {1, 2})
				g[h[i][k]].push_back({h[i][3-k], w});
		}
	}

	for(int &i : r[0]) i = INF;

	dfs_0(0), dfs_1(0);
}

int getMinimumFuelCapacity(int X, int Y) {
	int u = X, v = Y, qV = 0, rV = INF;

	if(d[u] > d[v]) swap(u, v);
	for(int i = 0; i < B; i++) {
		if((d[v] - d[u]) & (1<<i)) {
			qV = max(qV, q[v][i]);
			rV = min(rV, r[v][i]);
			v = p[v][i];
		}
	}
	if(u != v) {	
		for(int i = B; --i; ) {
			if(p[u][i] != p[v][i]) {
				qV = max({qV, q[u][i], q[v][i]});
				rV = min({rV, r[u][i], r[v][i]});
				u = p[u][i];
				v = p[v][i];
			}
		}
		qV = max({qV, q[u][0], q[v][0]});
		rV = min({rV, r[u][0], r[v][0]});
	}
	return rV == INF ? -1 : max(rV, qV);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 5 ms 8160 KB Output is correct
3 Correct 4 ms 8144 KB Output is correct
4 Correct 4 ms 8268 KB Output is correct
5 Correct 5 ms 8396 KB Output is correct
6 Correct 5 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 5 ms 8536 KB Output is correct
9 Correct 120 ms 37580 KB Output is correct
10 Correct 150 ms 46232 KB Output is correct
11 Correct 156 ms 45016 KB Output is correct
12 Correct 160 ms 47428 KB Output is correct
13 Correct 139 ms 50240 KB Output is correct
14 Correct 141 ms 36940 KB Output is correct
15 Correct 370 ms 50076 KB Output is correct
16 Correct 388 ms 46556 KB Output is correct
17 Correct 379 ms 54296 KB Output is correct
18 Correct 384 ms 52144 KB Output is correct
19 Correct 116 ms 19796 KB Output is correct
20 Correct 363 ms 50156 KB Output is correct
21 Correct 380 ms 47760 KB Output is correct
22 Correct 426 ms 52136 KB Output is correct
23 Correct 357 ms 52876 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 5 ms 8160 KB Output is correct
3 Incorrect 180 ms 40624 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 8140 KB Output is correct
2 Correct 5 ms 8160 KB Output is correct
3 Correct 4 ms 8144 KB Output is correct
4 Correct 4 ms 8268 KB Output is correct
5 Correct 5 ms 8396 KB Output is correct
6 Correct 5 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 5 ms 8536 KB Output is correct
9 Correct 5 ms 8140 KB Output is correct
10 Incorrect 7 ms 8424 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8160 KB Output is correct
4 Correct 4 ms 8144 KB Output is correct
5 Correct 4 ms 8268 KB Output is correct
6 Correct 5 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 5 ms 8396 KB Output is correct
9 Correct 5 ms 8536 KB Output is correct
10 Correct 120 ms 37580 KB Output is correct
11 Correct 150 ms 46232 KB Output is correct
12 Correct 156 ms 45016 KB Output is correct
13 Correct 160 ms 47428 KB Output is correct
14 Correct 139 ms 50240 KB Output is correct
15 Incorrect 7 ms 8424 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 8140 KB Output is correct
2 Correct 5 ms 8160 KB Output is correct
3 Correct 4 ms 8144 KB Output is correct
4 Correct 4 ms 8268 KB Output is correct
5 Correct 5 ms 8396 KB Output is correct
6 Correct 5 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 5 ms 8536 KB Output is correct
9 Correct 120 ms 37580 KB Output is correct
10 Correct 150 ms 46232 KB Output is correct
11 Correct 156 ms 45016 KB Output is correct
12 Correct 160 ms 47428 KB Output is correct
13 Correct 139 ms 50240 KB Output is correct
14 Correct 141 ms 36940 KB Output is correct
15 Correct 370 ms 50076 KB Output is correct
16 Correct 388 ms 46556 KB Output is correct
17 Correct 379 ms 54296 KB Output is correct
18 Correct 384 ms 52144 KB Output is correct
19 Incorrect 180 ms 40624 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8160 KB Output is correct
4 Correct 4 ms 8144 KB Output is correct
5 Correct 4 ms 8268 KB Output is correct
6 Correct 5 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 5 ms 8396 KB Output is correct
9 Correct 5 ms 8536 KB Output is correct
10 Correct 120 ms 37580 KB Output is correct
11 Correct 150 ms 46232 KB Output is correct
12 Correct 156 ms 45016 KB Output is correct
13 Correct 160 ms 47428 KB Output is correct
14 Correct 139 ms 50240 KB Output is correct
15 Correct 141 ms 36940 KB Output is correct
16 Correct 370 ms 50076 KB Output is correct
17 Correct 388 ms 46556 KB Output is correct
18 Correct 379 ms 54296 KB Output is correct
19 Correct 384 ms 52144 KB Output is correct
20 Incorrect 180 ms 40624 KB Output isn't correct
21 Halted 0 ms 0 KB -