oj.uz

Submission #871060

# Submission time Handle Problem Language Result Execution time Memory
871060 2023-11-09T19:35:10 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 272 ms 49512 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 = 22; 
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;
	graph[nds].push_back(u);
	reach[nds] = reach[u] || reach[v];
	if (u == v)
		reach[nds] = true;
	else {
		graph[nds].push_back(v);
		if (max(++deg[old_u], ++deg[old_v]) > 2)
			reach[nds] = true; 
	}
}

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 29164 KB Output is correct
3 Correct 3 ms 29016 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 71 ms 38608 KB Output is correct
10 Correct 87 ms 40904 KB Output is correct
11 Correct 90 ms 40588 KB Output is correct
12 Correct 90 ms 41380 KB Output is correct
13 Correct 78 ms 44512 KB Output is correct
14 Correct 73 ms 38852 KB Output is correct
15 Correct 241 ms 42812 KB Output is correct
16 Correct 178 ms 42356 KB Output is correct
17 Correct 199 ms 42960 KB Output is correct
18 Correct 272 ms 46216 KB Output is correct
19 Correct 81 ms 34576 KB Output is correct
20 Correct 189 ms 43892 KB Output is correct
21 Correct 213 ms 43648 KB Output is correct
22 Correct 198 ms 44328 KB Output is correct
23 Correct 237 ms 47664 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 29164 KB Output is correct
3 Incorrect 194 ms 49512 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 29164 KB Output is correct
3 Correct 3 ms 29016 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Incorrect 3 ms 29020 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 29020 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 29164 KB Output is correct
3 Correct 3 ms 29016 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29272 KB Output is correct
9 Correct 71 ms 38608 KB Output is correct
10 Correct 87 ms 40904 KB Output is correct
11 Correct 90 ms 40588 KB Output is correct
12 Correct 90 ms 41380 KB Output is correct
13 Correct 78 ms 44512 KB Output is correct
14 Correct 73 ms 38852 KB Output is correct
15 Correct 241 ms 42812 KB Output is correct
16 Correct 178 ms 42356 KB Output is correct
17 Correct 199 ms 42960 KB Output is correct
18 Correct 272 ms 46216 KB Output is correct
19 Incorrect 194 ms 49512 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 29020 KB Output isn't correct
2 Halted 0 ms 0 KB -