oj.uz

Submission #871160

# Submission time Handle Problem Language Result Execution time Memory
871160 2023-11-10T07:01:27 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 219 ms 53404 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 = 22; 
const ll MAXN = 1e5 + 100;
 
int par[3 * MAXN], deg[3 * MAXN], w[3 * MAXN], nds;
int depth[3 * MAXN], up[LOGN][3 * MAXN];
bool reach[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);
	
  deg[old_u]++, deg[old_v]++;
	par[nds] = nds;
	par[u] = par[v] = nds;
	graph[nds].push_back(u);
	reach[nds] = reach[u] || reach[v];
	if (u == v)
		reach[nds] = true;
	else {
		graph[nds].push_back(v);
		if (max(deg[old_u], deg[old_v]) > 2)
			reach[nds] = true; 
	}
}
 
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 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 4 ms 29016 KB Output is correct
2 Correct 3 ms 29172 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 3 ms 29016 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29280 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 40392 KB Output is correct
10 Correct 88 ms 42940 KB Output is correct
11 Correct 87 ms 42696 KB Output is correct
12 Correct 110 ms 43308 KB Output is correct
13 Correct 94 ms 46384 KB Output is correct
14 Correct 76 ms 40644 KB Output is correct
15 Correct 189 ms 46932 KB Output is correct
16 Correct 188 ms 46712 KB Output is correct
17 Correct 191 ms 47376 KB Output is correct
18 Correct 217 ms 50624 KB Output is correct
19 Correct 78 ms 36372 KB Output is correct
20 Correct 189 ms 48328 KB Output is correct
21 Correct 199 ms 48056 KB Output is correct
22 Correct 192 ms 48800 KB Output is correct
23 Correct 219 ms 51984 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 29172 KB Output is correct
3 Incorrect 168 ms 53404 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 29172 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 3 ms 29016 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29280 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 4 ms 29016 KB Output is correct
2 Correct 3 ms 29172 KB Output is correct
3 Correct 4 ms 29020 KB Output is correct
4 Correct 3 ms 29016 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 4 ms 29280 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 40392 KB Output is correct
10 Correct 88 ms 42940 KB Output is correct
11 Correct 87 ms 42696 KB Output is correct
12 Correct 110 ms 43308 KB Output is correct
13 Correct 94 ms 46384 KB Output is correct
14 Correct 76 ms 40644 KB Output is correct
15 Correct 189 ms 46932 KB Output is correct
16 Correct 188 ms 46712 KB Output is correct
17 Correct 191 ms 47376 KB Output is correct
18 Correct 217 ms 50624 KB Output is correct
19 Incorrect 168 ms 53404 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 -