oj.uz

Submission #568582

# Submission time Handle Problem Language Result Execution time Memory
568582 2022-05-25T17:52:15 Z _karan_gandhi Swapping Cities (APIO20_swap) C++17
0 / 100
 578 ms 50948 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();
		// cout << pl(best.top()) << endl;
	}

	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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 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 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 148 ms 33680 KB Output is correct
10 Correct 206 ms 44156 KB Output is correct
11 Correct 191 ms 42304 KB Output is correct
12 Correct 212 ms 45456 KB Output is correct
13 Correct 211 ms 49340 KB Output is correct
14 Correct 165 ms 32380 KB Output is correct
15 Correct 480 ms 45452 KB Output is correct
16 Correct 447 ms 40856 KB Output is correct
17 Correct 578 ms 50948 KB Output is correct
18 Correct 464 ms 47908 KB Output is correct
19 Runtime error 45 ms 3652 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 206 ms 34492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 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 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Runtime error 1 ms 348 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 348 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 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 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 148 ms 33680 KB Output is correct
10 Correct 206 ms 44156 KB Output is correct
11 Correct 191 ms 42304 KB Output is correct
12 Correct 212 ms 45456 KB Output is correct
13 Correct 211 ms 49340 KB Output is correct
14 Correct 165 ms 32380 KB Output is correct
15 Correct 480 ms 45452 KB Output is correct
16 Correct 447 ms 40856 KB Output is correct
17 Correct 578 ms 50948 KB Output is correct
18 Correct 464 ms 47908 KB Output is correct
19 Incorrect 206 ms 34492 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 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -