oj.uz

Submission #871001

# Submission time Handle Problem Language Result Execution time Memory
871001 2023-11-09T16:49:57 Z serifefedartar Swapping Cities (APIO20_swap) C++17
0 / 100
 179 ms 34648 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][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) {
	u = find(u), v = find(v);
	par[nds] = nds;
	par[u] = par[v] = nds;

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

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]);

	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 i = 0; i < LOGN; i++)
		up[i][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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10708 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10860 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 56 ms 22728 KB Output is correct
10 Correct 66 ms 25276 KB Output is correct
11 Correct 65 ms 25056 KB Output is correct
12 Correct 67 ms 25884 KB Output is correct
13 Correct 66 ms 29128 KB Output is correct
14 Correct 78 ms 23080 KB Output is correct
15 Correct 136 ms 29500 KB Output is correct
16 Correct 135 ms 29048 KB Output is correct
17 Correct 140 ms 30000 KB Output is correct
18 Correct 179 ms 33224 KB Output is correct
19 Correct 72 ms 18216 KB Output is correct
20 Incorrect 133 ms 29356 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10708 KB Output is correct
3 Incorrect 152 ms 34648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10708 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10860 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Incorrect 1 ms 10588 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10708 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10860 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 56 ms 22728 KB Output is correct
10 Correct 66 ms 25276 KB Output is correct
11 Correct 65 ms 25056 KB Output is correct
12 Correct 67 ms 25884 KB Output is correct
13 Correct 66 ms 29128 KB Output is correct
14 Correct 78 ms 23080 KB Output is correct
15 Correct 136 ms 29500 KB Output is correct
16 Correct 135 ms 29048 KB Output is correct
17 Correct 140 ms 30000 KB Output is correct
18 Correct 179 ms 33224 KB Output is correct
19 Incorrect 152 ms 34648 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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