oj.uz

Submission #975196

# Submission time Handle Problem Language Result Execution time Memory
975196 2024-05-04T14:42:30 Z XXBabaProBerkay Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 524288 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second

using ll = long long;

const int INF = 1e9 + 7;

vector<int> dpth;
vector<vector<pair<int, int>>> adj;
vector<array<int, 20>> up, ans, res;

void DFS(int k, int p, int x);

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
	adj.resize(N);
	dpth.resize(N);
	up = ans = res = vector<array<int, 20>>(N);
	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]);
	}

	res[0][0] = INF;
	DFS(0, 0, INF);
}

void DFS(int k, int p, int x)
{
	dpth[k] = dpth[p] + 1;
	up[k][0] = p;
	ans[k][0] = x;
	for (int i = 1; i < 20; i++)
	{
		up[k][i] = up[up[k][i - 1]][i - 1];
		ans[k][i] = min(ans[k][i - 1], ans[up[k][i - 1]][i - 1]);
		res[k][i] = max(res[k][i - 1], res[up[k][i - 1]][i - 1]);
	}

	int mn = INF, mn2 = INF;
	for (pair<int, int> i : adj[k])
		if (i.F == p)
			continue;
		else if (i.S < mn)
		{
			mn2 = mn;
			mn = i.S;
		}
		else if (i.S < mn2)
			mn2 = i.S;

	for (pair<int, int> i : adj[k])
	{
		if (i.F == p)
			continue;

		res[i.F][0] = i.S;

		if (i.S == mn)
			DFS(i.F, k, mn2);
		else
			DFS(i.F, k, mn);
	}
}

array<int, 3> kth_ancestor(int a, int x)
{
	int as = INF, rs = -INF;
	for (int i = 0; i < 20; i++)
	{
		if (x & (1 << i))
		{
			as = min(as, ans[a][i]);
			rs = max(rs, res[a][i]);
			a = up[a][i];
		}
	}

	return {a, as, rs};
}

int getMinimumFuelCapacity(int X, int Y)
{
	if (dpth[X] < dpth[Y])
		swap(X, Y);

	int X0 = X, Y0 = Y;
	array<int, 3> ret = kth_ancestor(X, dpth[X] - dpth[Y]);

	if (ret[0] == Y)
		return (ret[1] == INF ? -1 : max(ret[1], ret[2]));

	X = ret[0];

	for (int i = 19; i >= 0; i--)
		if (up[X][i] != up[Y][i])
			X = up[X][i], Y = up[Y][i];

	array<int, 3> rs1 = kth_ancestor(X0, dpth[X0] - dpth[X]);
	array<int, 3> rs2 = kth_ancestor(Y0, dpth[Y0] - dpth[Y]);

	int mn = INF, x = -INF, y = -INF;
	for (pair<int, int> i : adj[up[X][0]])
	{
		if (i.F == X)
		{
			x = i.S;
			continue;
		}
		if (i.F == Y)
		{
			y = i.S;
			continue;
		}

		if (i.F == up[up[X][0]][0])
			continue;

		mn = min(mn, i.S);
	}

	rs1[1] = min(rs1[1], mn);
	rs1[2] = max(rs1[2], x);
	rs2[2] = max(rs2[2], y);
	return (rs1[1] != INF || rs2[1] != INF ? max(max(rs1[2], rs2[2]), min(rs1[1], rs2[1])) : -1);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 112 ms 29352 KB Output is correct
10 Correct 111 ms 36668 KB Output is correct
11 Correct 107 ms 35668 KB Output is correct
12 Correct 121 ms 38044 KB Output is correct
13 Correct 137 ms 39472 KB Output is correct
14 Correct 110 ms 29100 KB Output is correct
15 Incorrect 335 ms 39892 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 2039 ms 34736 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Runtime error 1196 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1196 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 112 ms 29352 KB Output is correct
10 Correct 111 ms 36668 KB Output is correct
11 Correct 107 ms 35668 KB Output is correct
12 Correct 121 ms 38044 KB Output is correct
13 Correct 137 ms 39472 KB Output is correct
14 Correct 110 ms 29100 KB Output is correct
15 Incorrect 335 ms 39892 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1196 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -