oj.uz

답안 #871014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871014 2023-11-09T17:20:22 Z serifefedartar 자매 도시 (APIO20_swap) C++17
6 / 100
 252 ms 47660 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) {
	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 = 1; i <= N + M; i++) {
		if (i == find(i)) {
			for (int j = 0; j < LOGN; j++)
				up[j][i] = i;

			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 4 ms 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 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 4 ms 29276 KB Output is correct
9 Correct 69 ms 38100 KB Output is correct
10 Correct 95 ms 40136 KB Output is correct
11 Correct 87 ms 40120 KB Output is correct
12 Correct 88 ms 40640 KB Output is correct
13 Correct 75 ms 43720 KB Output is correct
14 Correct 83 ms 38336 KB Output is correct
15 Correct 202 ms 42068 KB Output is correct
16 Correct 208 ms 41680 KB Output is correct
17 Correct 213 ms 42480 KB Output is correct
18 Correct 192 ms 45616 KB Output is correct
19 Correct 85 ms 34316 KB Output is correct
20 Correct 202 ms 43304 KB Output is correct
21 Correct 184 ms 43140 KB Output is correct
22 Correct 252 ms 43760 KB Output is correct
23 Correct 209 ms 47080 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 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 4 ms 29276 KB Output is correct
9 Correct 69 ms 38100 KB Output is correct
10 Correct 95 ms 40136 KB Output is correct
11 Correct 87 ms 40120 KB Output is correct
12 Correct 88 ms 40640 KB Output is correct
13 Correct 75 ms 43720 KB Output is correct
14 Correct 83 ms 38336 KB Output is correct
15 Correct 202 ms 42068 KB Output is correct
16 Correct 208 ms 41680 KB Output is correct
17 Correct 213 ms 42480 KB Output is correct
18 Correct 192 ms 45616 KB Output is correct
19 Incorrect 168 ms 47660 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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