oj.uz

Submission #871013

# Submission time Handle Problem Language Result Execution time Memory
871013 2023-11-09T17:19:24 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 222 ms 49992 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 = 1; i <= N + M; i++) {
		if (i == find(i)) {
			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 29016 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 3 ms 29120 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 29276 KB Output is correct
9 Correct 74 ms 39132 KB Output is correct
10 Correct 92 ms 41412 KB Output is correct
11 Correct 84 ms 41160 KB Output is correct
12 Correct 90 ms 41924 KB Output is correct
13 Correct 82 ms 45012 KB Output is correct
14 Correct 74 ms 39428 KB Output is correct
15 Correct 174 ms 44368 KB Output is correct
16 Correct 180 ms 44152 KB Output is correct
17 Correct 185 ms 45024 KB Output is correct
18 Correct 222 ms 48160 KB Output is correct
19 Correct 77 ms 35604 KB Output is correct
20 Correct 172 ms 45636 KB Output is correct
21 Correct 172 ms 45324 KB Output is correct
22 Correct 190 ms 46532 KB Output is correct
23 Correct 197 ms 49456 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29016 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Incorrect 178 ms 49992 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 29016 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 3 ms 29120 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 29276 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 3 ms 29016 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 3 ms 29120 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 29276 KB Output is correct
9 Correct 74 ms 39132 KB Output is correct
10 Correct 92 ms 41412 KB Output is correct
11 Correct 84 ms 41160 KB Output is correct
12 Correct 90 ms 41924 KB Output is correct
13 Correct 82 ms 45012 KB Output is correct
14 Correct 74 ms 39428 KB Output is correct
15 Correct 174 ms 44368 KB Output is correct
16 Correct 180 ms 44152 KB Output is correct
17 Correct 185 ms 45024 KB Output is correct
18 Correct 222 ms 48160 KB Output is correct
19 Incorrect 178 ms 49992 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 -