oj.uz

답안 #871051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871051 2023-11-09T19:02:16 Z serifefedartar 자매 도시 (APIO20_swap) C++17
6 / 100
 210 ms 47400 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] || (u == v);
	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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 4 ms 25188 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 25188 KB Output is correct
9 Correct 71 ms 36736 KB Output is correct
10 Correct 80 ms 38856 KB Output is correct
11 Correct 90 ms 38684 KB Output is correct
12 Correct 91 ms 39112 KB Output is correct
13 Correct 75 ms 42340 KB Output is correct
14 Correct 71 ms 36856 KB Output is correct
15 Correct 199 ms 40772 KB Output is correct
16 Correct 190 ms 40260 KB Output is correct
17 Correct 187 ms 41016 KB Output is correct
18 Correct 189 ms 44076 KB Output is correct
19 Correct 75 ms 32356 KB Output is correct
20 Correct 185 ms 41860 KB Output is correct
21 Correct 191 ms 41560 KB Output is correct
22 Correct 179 ms 42296 KB Output is correct
23 Correct 210 ms 45436 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24920 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Incorrect 155 ms 47400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 4 ms 25188 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 25188 KB Output is correct
9 Incorrect 3 ms 24920 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 4 ms 25188 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 25188 KB Output is correct
9 Correct 71 ms 36736 KB Output is correct
10 Correct 80 ms 38856 KB Output is correct
11 Correct 90 ms 38684 KB Output is correct
12 Correct 91 ms 39112 KB Output is correct
13 Correct 75 ms 42340 KB Output is correct
14 Correct 71 ms 36856 KB Output is correct
15 Correct 199 ms 40772 KB Output is correct
16 Correct 190 ms 40260 KB Output is correct
17 Correct 187 ms 41016 KB Output is correct
18 Correct 189 ms 44076 KB Output is correct
19 Incorrect 155 ms 47400 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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