oj.uz

Submission #871049

# Submission time Handle Problem Language Result Execution time Memory
871049 2023-11-09T18:58:21 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 219 ms 52396 KB 
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 100;

int par[3 * MAXN], reach[3 * MAXN], deg[3 * MAXN], w[3 * MAXN], nds;
int depth[3 * MAXN], up[LOGN][3 * MAXN];
vector<pair<int,pair<int,int>>> edges;
vector<vector<int>> graph;
int find(int node) {
	if (node == par[node])
		return node;
	return par[node] = find(par[node]);
}

void addEdge(int u, int v) {
	int old_u = u, old_v = v;
	u = find(u), v = find(v);
	par[nds] = nds;
	par[u] = par[v] = nds;

	graph[nds].push_back(u);
	reach[nds] = reach[u] || reach[v] || (u == v);
	if (u != v) {
		graph[nds].push_back(v);
		reach[nds] |= (max(++deg[old_u], ++deg[old_v]) > 2);
	}
}

void dfs(int node) {
	for (auto u : graph[node]) {
		depth[u] = depth[node] + 1;
		up[0][u] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u] = up[i-1][up[i-1][u]];
		dfs(u);
	}
}

int find(int node, int k) {
	for (int i = LOGN-1; i >= 0; i--) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int u, int v) {
	if (depth[v] > depth[u])
		swap(u, v);
	u = find(u, depth[u] - depth[v]);

	if (u == v)
		return u;

	for (int i = LOGN - 1; i >= 0; i--) {
		if (up[i][u] != up[i][v]) {
			u = up[i][u];
			v = up[i][v];
		}
	}
	return up[0][u];
}

int first_active(int node) {
	if (reach[node])
		return node;
	for (int i = LOGN - 1; i >= 0; i--) {
		if (reach[up[i][node]] == 0)
			node = up[i][node];
	}
	return up[0][node];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	nds = N;
	graph = vector<vector<int>>(N+M+1, vector<int>());
	for (int i = 1; i <= N; i++)
		par[i] = i;
	for (int i = 0; i < M; i++)
		edges.push_back({W[i], {U[i] + 1, V[i] + 1}});
	sort(edges.begin(), edges.end());

	for (int i = 0; i < M; i++) {
		nds++;
		w[nds] = edges[i].f;
		addEdge(edges[i].s.f, edges[i].s.s);
	}

	for (int j = 0; j < LOGN; j++)
		up[j][nds] = nds;
	dfs(nds);
}

int getMinimumFuelCapacity(int X, int Y) {
	int Q = first_active(lca(X, Y));
	if (reach[Q])
		return w[Q];
	else
		return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 4 ms 29128 KB Output is correct
6 Correct 4 ms 29136 KB Output is correct
7 Correct 4 ms 29272 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 71 ms 39912 KB Output is correct
10 Correct 81 ms 42344 KB Output is correct
11 Correct 81 ms 41928 KB Output is correct
12 Correct 85 ms 42696 KB Output is correct
13 Correct 75 ms 46024 KB Output is correct
14 Correct 71 ms 40032 KB Output is correct
15 Correct 219 ms 45900 KB Output is correct
16 Correct 169 ms 45684 KB Output is correct
17 Correct 187 ms 46740 KB Output is correct
18 Correct 190 ms 49724 KB Output is correct
19 Correct 78 ms 36372 KB Output is correct
20 Correct 193 ms 47144 KB Output is correct
21 Correct 194 ms 46840 KB Output is correct
22 Correct 180 ms 47916 KB Output is correct
23 Correct 197 ms 50980 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 4 ms 29128 KB Output is correct
6 Correct 4 ms 29136 KB Output is correct
7 Correct 4 ms 29272 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Incorrect 3 ms 29116 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 29116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29020 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 4 ms 29128 KB Output is correct
6 Correct 4 ms 29136 KB Output is correct
7 Correct 4 ms 29272 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 71 ms 39912 KB Output is correct
10 Correct 81 ms 42344 KB Output is correct
11 Correct 81 ms 41928 KB Output is correct
12 Correct 85 ms 42696 KB Output is correct
13 Correct 75 ms 46024 KB Output is correct
14 Correct 71 ms 40032 KB Output is correct
15 Correct 219 ms 45900 KB Output is correct
16 Correct 169 ms 45684 KB Output is correct
17 Correct 187 ms 46740 KB Output is correct
18 Correct 190 ms 49724 KB Output is correct
19 Incorrect 171 ms 52396 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 29116 KB Output isn't correct
2 Halted 0 ms 0 KB -