oj.uz

Submission #568576

# Submission time Handle Problem Language Result Execution time Memory
568576 2022-05-25T17:40:38 Z _karan_gandhi Swapping Cities (APIO20_swap) C++17
0 / 100
 488 ms 55368 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

int n, m;
// vector<int> _u, _v, w;
vector<int> dp, dep;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> jumpNode, jumpMax;
const int LOG = 20;
int inf = 1e9 + 7;

void dfs(int u, int par, int wt) {
	if (u != par) dep[u] = dep[par] + 1;
	else dep[u] = 0;

	jumpNode[u][0] = par;
	if (wt != -1) jumpMax[u][0] = wt;

	if (adj[u].size() >= 3) {
		priority_queue<int> best;
		for (auto [_, _wt] : adj[u]) best.push(_wt);
		best.pop();
		best.pop();
		dp[u] = best.top();
	}

	for (auto [v, _wt] : adj[u]) {
		if (v == par) continue;

		dfs(v, u, _wt);
	}

	for (auto [v, _] : adj[u]) {
		if (v == par) continue;
		dp[u] = min(dp[u], max(dp[v], _));
		dp[v] = min(dp[v], max(dp[u], _));
	}
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	// solve the tree case
	// get the max on the path from u to v <- log(n)
	n = N;
	m = M;
	assert(m == n - 1); // just the tree case

	dp = vector<int>(n, inf);
	// dp.resize(n);
	adj.resize(n);
	dep.resize(n);

	jumpNode = vector<vector<int>>(n, vector<int>(LOG));
	jumpMax = vector<vector<int>>(n, vector<int>(LOG));

	for (int i = 0; i < m; i++) {
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
	}

	dfs(0, 0, -1);

	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < n; j++) {
			jumpNode[j][i] = jumpNode[jumpNode[j][i - 1]][i - 1];
			jumpMax[j][i] = max(jumpMax[j][i - 1], jumpMax[jumpNode[j][i - 1]][i - 1]);
		}
	}
}

pair<int, int> kth(int a, int k) {
	int res = 0;
	int pow = LOG - 1;
	while (k > 0) {
		if (k < (1 << pow)) pow--;
		res = max(res, jumpMax[a][pow]);
		a = jumpNode[a][pow];

		k -= (1 << k);
	}

	return make_pair(a, res);
}

int get_cost(int a, int b) {
	int res = 0;

	if (dep[a] < dep[b]) {
		swap(a, b);
	}

	pair<int, int> rres = kth(a, dep[a] - dep[b]);
	res = rres.second;
	a = rres.first;
	int pow = LOG - 1;

	if (a == b) {
		return res;
	}

	while (pow >= 0) {
		if (jumpNode[a][pow] != jumpNode[b][pow]) {
			res = max({
				res,
				jumpMax[a][pow],
				jumpMax[b][pow]
			});

			a = jumpNode[a][pow];
			b = jumpNode[b][pow];
		}

		pow--;
	}

	return res;
}

int getMinimumFuelCapacity(int x, int y) {
	if (n == 2) return -1;

	int res = max(dp[x], get_cost(x, y));
	return res >= inf ? -1 : res;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 712 KB Output is correct
9 Correct 148 ms 35384 KB Output is correct
10 Correct 174 ms 46184 KB Output is correct
11 Correct 176 ms 44336 KB Output is correct
12 Correct 225 ms 47572 KB Output is correct
13 Correct 174 ms 51404 KB Output is correct
14 Correct 175 ms 34244 KB Output is correct
15 Correct 416 ms 49860 KB Output is correct
16 Correct 385 ms 45124 KB Output is correct
17 Correct 469 ms 55368 KB Output is correct
18 Correct 488 ms 52412 KB Output is correct
19 Runtime error 31 ms 5708 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 210 ms 38368 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 712 KB Output is correct
9 Runtime error 1 ms 340 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 712 KB Output is correct
9 Correct 148 ms 35384 KB Output is correct
10 Correct 174 ms 46184 KB Output is correct
11 Correct 176 ms 44336 KB Output is correct
12 Correct 225 ms 47572 KB Output is correct
13 Correct 174 ms 51404 KB Output is correct
14 Correct 175 ms 34244 KB Output is correct
15 Correct 416 ms 49860 KB Output is correct
16 Correct 385 ms 45124 KB Output is correct
17 Correct 469 ms 55368 KB Output is correct
18 Correct 488 ms 52412 KB Output is correct
19 Incorrect 210 ms 38368 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -