oj.uz

Submission #871058

# Submission time Handle Problem Language Result Execution time Memory
871058 2023-11-09T19:32:12 Z serifefedartar Swapping Cities (APIO20_swap) C++17
6 / 100
 227 ms 51540 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], 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);
	
	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 6 ms 24920 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 24924 KB Output is correct
5 Correct 3 ms 25180 KB Output is correct
6 Correct 3 ms 25180 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 3 ms 25036 KB Output is correct
9 Correct 78 ms 38352 KB Output is correct
10 Correct 88 ms 40648 KB Output is correct
11 Correct 86 ms 40676 KB Output is correct
12 Correct 92 ms 41416 KB Output is correct
13 Correct 77 ms 44488 KB Output is correct
14 Correct 71 ms 38596 KB Output is correct
15 Correct 183 ms 44852 KB Output is correct
16 Correct 181 ms 44720 KB Output is correct
17 Correct 202 ms 45432 KB Output is correct
18 Correct 204 ms 48432 KB Output is correct
19 Correct 76 ms 34580 KB Output is correct
20 Correct 185 ms 45888 KB Output is correct
21 Correct 217 ms 45960 KB Output is correct
22 Correct 205 ms 46892 KB Output is correct
23 Correct 227 ms 49964 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24920 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Incorrect 201 ms 51540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24920 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 24924 KB Output is correct
5 Correct 3 ms 25180 KB Output is correct
6 Correct 3 ms 25180 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 3 ms 25036 KB Output is correct
9 Incorrect 3 ms 24924 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 24924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24920 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 24924 KB Output is correct
5 Correct 3 ms 25180 KB Output is correct
6 Correct 3 ms 25180 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 3 ms 25036 KB Output is correct
9 Correct 78 ms 38352 KB Output is correct
10 Correct 88 ms 40648 KB Output is correct
11 Correct 86 ms 40676 KB Output is correct
12 Correct 92 ms 41416 KB Output is correct
13 Correct 77 ms 44488 KB Output is correct
14 Correct 71 ms 38596 KB Output is correct
15 Correct 183 ms 44852 KB Output is correct
16 Correct 181 ms 44720 KB Output is correct
17 Correct 202 ms 45432 KB Output is correct
18 Correct 204 ms 48432 KB Output is correct
19 Incorrect 201 ms 51540 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 24924 KB Output isn't correct
2 Halted 0 ms 0 KB -