oj.uz

Submission #871055

# Submission time Handle Problem Language Result Execution time Memory
871055 2023-11-09T19:24:26 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 192 ms 47720 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], deg[3 * MAXN], w[3 * MAXN], nds;
int depth[3 * MAXN], up[LOGN][3 * MAXN];
bool reach[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;

	deg[old_v]++, deg[old_u]++;

	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 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 24920 KB Output is correct
5 Correct 3 ms 25176 KB Output is correct
6 Correct 3 ms 25028 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 4 ms 25180 KB Output is correct
9 Correct 63 ms 36736 KB Output is correct
10 Correct 84 ms 38864 KB Output is correct
11 Correct 78 ms 38680 KB Output is correct
12 Correct 86 ms 39104 KB Output is correct
13 Correct 74 ms 42432 KB Output is correct
14 Correct 69 ms 36804 KB Output is correct
15 Correct 192 ms 40528 KB Output is correct
16 Correct 174 ms 40308 KB Output is correct
17 Correct 177 ms 41036 KB Output is correct
18 Correct 186 ms 44084 KB Output is correct
19 Correct 75 ms 32532 KB Output is correct
20 Correct 166 ms 41860 KB Output is correct
21 Correct 178 ms 41600 KB Output is correct
22 Correct 174 ms 42308 KB Output is correct
23 Correct 184 ms 45608 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Incorrect 157 ms 47720 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 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 24920 KB Output is correct
5 Correct 3 ms 25176 KB Output is correct
6 Correct 3 ms 25028 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 4 ms 25180 KB Output is correct
9 Incorrect 3 ms 24924 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 24924 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 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 24920 KB Output is correct
5 Correct 3 ms 25176 KB Output is correct
6 Correct 3 ms 25028 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 4 ms 25180 KB Output is correct
9 Correct 63 ms 36736 KB Output is correct
10 Correct 84 ms 38864 KB Output is correct
11 Correct 78 ms 38680 KB Output is correct
12 Correct 86 ms 39104 KB Output is correct
13 Correct 74 ms 42432 KB Output is correct
14 Correct 69 ms 36804 KB Output is correct
15 Correct 192 ms 40528 KB Output is correct
16 Correct 174 ms 40308 KB Output is correct
17 Correct 177 ms 41036 KB Output is correct
18 Correct 186 ms 44084 KB Output is correct
19 Incorrect 157 ms 47720 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 24924 KB Output isn't correct
2 Halted 0 ms 0 KB -