oj.uz

Submission #871020

# Submission time Handle Problem Language Result Execution time Memory
871020 2023-11-09T17:37:35 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 208 ms 49004 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) {
	int old_u = u, old_v = v;
	u = find(u), v = find(v);
	par[nds] = nds;
	par[u] = par[v] = nds;

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

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 5 ms 29020 KB Output is correct
2 Correct 3 ms 29016 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29168 KB Output is correct
5 Correct 4 ms 29284 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 65 ms 38252 KB Output is correct
10 Correct 86 ms 40108 KB Output is correct
11 Correct 88 ms 40084 KB Output is correct
12 Correct 91 ms 40664 KB Output is correct
13 Correct 76 ms 43716 KB Output is correct
14 Correct 78 ms 38344 KB Output is correct
15 Correct 177 ms 42064 KB Output is correct
16 Correct 178 ms 41664 KB Output is correct
17 Correct 189 ms 42456 KB Output is correct
18 Correct 204 ms 45612 KB Output is correct
19 Correct 78 ms 34584 KB Output is correct
20 Correct 171 ms 43336 KB Output is correct
21 Correct 180 ms 43064 KB Output is correct
22 Correct 194 ms 43808 KB Output is correct
23 Correct 208 ms 46892 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 3 ms 29016 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29168 KB Output is correct
5 Correct 4 ms 29284 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 4 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 4 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 5 ms 29020 KB Output is correct
2 Correct 3 ms 29016 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 4 ms 29168 KB Output is correct
5 Correct 4 ms 29284 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 65 ms 38252 KB Output is correct
10 Correct 86 ms 40108 KB Output is correct
11 Correct 88 ms 40084 KB Output is correct
12 Correct 91 ms 40664 KB Output is correct
13 Correct 76 ms 43716 KB Output is correct
14 Correct 78 ms 38344 KB Output is correct
15 Correct 177 ms 42064 KB Output is correct
16 Correct 178 ms 41664 KB Output is correct
17 Correct 189 ms 42456 KB Output is correct
18 Correct 204 ms 45612 KB Output is correct
19 Incorrect 180 ms 49004 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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