oj.uz

Submission #871003

# Submission time Handle Problem Language Result Execution time Memory
871003 2023-11-09T16:57:05 Z serifefedartar Swapping Cities (APIO20_swap) C++17
0 / 100
 172 ms 30736 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]);

	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;
	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 1 ms 10840 KB Output is correct
2 Correct 1 ms 10588 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 10588 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 64 ms 21180 KB Output is correct
10 Correct 63 ms 23240 KB Output is correct
11 Correct 69 ms 22980 KB Output is correct
12 Correct 66 ms 23748 KB Output is correct
13 Correct 65 ms 27076 KB Output is correct
14 Correct 77 ms 21216 KB Output is correct
15 Correct 132 ms 25168 KB Output is correct
16 Correct 131 ms 24888 KB Output is correct
17 Correct 143 ms 25672 KB Output is correct
18 Correct 172 ms 28684 KB Output is correct
19 Correct 73 ms 16148 KB Output is correct
20 Incorrect 132 ms 25064 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Correct 1 ms 10588 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 10588 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Incorrect 2 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 2 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 1 ms 10840 KB Output is correct
2 Correct 1 ms 10588 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 10588 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 64 ms 21180 KB Output is correct
10 Correct 63 ms 23240 KB Output is correct
11 Correct 69 ms 22980 KB Output is correct
12 Correct 66 ms 23748 KB Output is correct
13 Correct 65 ms 27076 KB Output is correct
14 Correct 77 ms 21216 KB Output is correct
15 Correct 132 ms 25168 KB Output is correct
16 Correct 131 ms 24888 KB Output is correct
17 Correct 143 ms 25672 KB Output is correct
18 Correct 172 ms 28684 KB Output is correct
19 Incorrect 151 ms 30736 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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