oj.uz

Submission #871015

# Submission time Handle Problem Language Result Execution time Memory
871015 2023-11-09T17:21:04 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 285 ms 47728 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][i] = i;

			dfs(i);
		}
	}
}

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 3 ms 29020 KB Output is correct
3 Correct 3 ms 29124 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 29032 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 65 ms 38192 KB Output is correct
10 Correct 91 ms 40220 KB Output is correct
11 Correct 86 ms 40120 KB Output is correct
12 Correct 95 ms 40648 KB Output is correct
13 Correct 81 ms 43716 KB Output is correct
14 Correct 76 ms 38188 KB Output is correct
15 Correct 231 ms 42116 KB Output is correct
16 Correct 172 ms 41784 KB Output is correct
17 Correct 184 ms 42524 KB Output is correct
18 Correct 219 ms 45604 KB Output is correct
19 Correct 76 ms 34340 KB Output is correct
20 Correct 172 ms 43312 KB Output is correct
21 Correct 196 ms 43136 KB Output is correct
22 Correct 196 ms 43860 KB Output is correct
23 Correct 285 ms 47288 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 3 ms 29020 KB Output is correct
3 Incorrect 170 ms 47728 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 3 ms 29020 KB Output is correct
3 Correct 3 ms 29124 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 29032 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 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 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29124 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 29032 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 65 ms 38192 KB Output is correct
10 Correct 91 ms 40220 KB Output is correct
11 Correct 86 ms 40120 KB Output is correct
12 Correct 95 ms 40648 KB Output is correct
13 Correct 81 ms 43716 KB Output is correct
14 Correct 76 ms 38188 KB Output is correct
15 Correct 231 ms 42116 KB Output is correct
16 Correct 172 ms 41784 KB Output is correct
17 Correct 184 ms 42524 KB Output is correct
18 Correct 219 ms 45604 KB Output is correct
19 Incorrect 170 ms 47728 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 -