oj.uz

Submission #871012

# Submission time Handle Problem Language Result Execution time Memory
871012 2023-11-09T17:18:12 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 222 ms 47724 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) {
	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]);

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

	for (int i = 1; i <= N + M; i++) {
		if (i == find(i))
			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 4 ms 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 4 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 5 ms 29288 KB Output is correct
9 Correct 71 ms 38260 KB Output is correct
10 Correct 100 ms 40160 KB Output is correct
11 Correct 94 ms 40064 KB Output is correct
12 Correct 91 ms 40644 KB Output is correct
13 Correct 80 ms 43724 KB Output is correct
14 Correct 78 ms 38340 KB Output is correct
15 Correct 222 ms 42068 KB Output is correct
16 Correct 180 ms 41848 KB Output is correct
17 Correct 202 ms 42356 KB Output is correct
18 Correct 219 ms 45916 KB Output is correct
19 Correct 76 ms 34316 KB Output is correct
20 Correct 198 ms 43200 KB Output is correct
21 Correct 185 ms 43136 KB Output is correct
22 Correct 202 ms 43824 KB Output is correct
23 Correct 221 ms 46892 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 4 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 5 ms 29288 KB Output is correct
9 Incorrect 3 ms 29016 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 29016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 4 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 5 ms 29288 KB Output is correct
9 Correct 71 ms 38260 KB Output is correct
10 Correct 100 ms 40160 KB Output is correct
11 Correct 94 ms 40064 KB Output is correct
12 Correct 91 ms 40644 KB Output is correct
13 Correct 80 ms 43724 KB Output is correct
14 Correct 78 ms 38340 KB Output is correct
15 Correct 222 ms 42068 KB Output is correct
16 Correct 180 ms 41848 KB Output is correct
17 Correct 202 ms 42356 KB Output is correct
18 Correct 219 ms 45916 KB Output is correct
19 Incorrect 191 ms 47724 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 29016 KB Output isn't correct
2 Halted 0 ms 0 KB -