oj.uz

답안 #871017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871017 2023-11-09T17:35:41 Z serifefedartar 자매 도시 (APIO20_swap) C++17
6 / 100
 225 ms 48888 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] = (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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 4 ms 29172 KB Output is correct
4 Correct 5 ms 29232 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 5 ms 29276 KB Output is correct
9 Correct 73 ms 38260 KB Output is correct
10 Correct 90 ms 40132 KB Output is correct
11 Correct 88 ms 40120 KB Output is correct
12 Correct 93 ms 40644 KB Output is correct
13 Correct 78 ms 43760 KB Output is correct
14 Correct 74 ms 38352 KB Output is correct
15 Correct 183 ms 42068 KB Output is correct
16 Correct 179 ms 41788 KB Output is correct
17 Correct 223 ms 42648 KB Output is correct
18 Correct 213 ms 45628 KB Output is correct
19 Correct 78 ms 34576 KB Output is correct
20 Correct 190 ms 43280 KB Output is correct
21 Correct 185 ms 43084 KB Output is correct
22 Correct 225 ms 43760 KB Output is correct
23 Correct 207 ms 47020 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Incorrect 160 ms 48888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 4 ms 29172 KB Output is correct
4 Correct 5 ms 29232 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 5 ms 29276 KB Output is correct
9 Incorrect 3 ms 29268 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 29268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 4 ms 29172 KB Output is correct
4 Correct 5 ms 29232 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 5 ms 29276 KB Output is correct
9 Correct 73 ms 38260 KB Output is correct
10 Correct 90 ms 40132 KB Output is correct
11 Correct 88 ms 40120 KB Output is correct
12 Correct 93 ms 40644 KB Output is correct
13 Correct 78 ms 43760 KB Output is correct
14 Correct 74 ms 38352 KB Output is correct
15 Correct 183 ms 42068 KB Output is correct
16 Correct 179 ms 41788 KB Output is correct
17 Correct 223 ms 42648 KB Output is correct
18 Correct 213 ms 45628 KB Output is correct
19 Incorrect 160 ms 48888 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 29268 KB Output isn't correct
2 Halted 0 ms 0 KB -