oj.uz

답안 #871023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871023 2023-11-09T17:46:00 Z serifefedartar 자매 도시 (APIO20_swap) C++17
6 / 100
 207 ms 48884 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;

	graph[nds].push_back(u);
	reach[nds] = reach[u] || reach[v] || (u == v);
	if (u != v) {
		graph[nds].push_back(v);
		if (max(++deg[old_u], ++deg[old_v]) > 2)
			reach[nds] = true;
	} else {
		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 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 29016 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 4 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 29280 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 65 ms 38088 KB Output is correct
10 Correct 84 ms 40136 KB Output is correct
11 Correct 83 ms 40124 KB Output is correct
12 Correct 106 ms 40784 KB Output is correct
13 Correct 91 ms 43988 KB Output is correct
14 Correct 79 ms 38344 KB Output is correct
15 Correct 199 ms 42108 KB Output is correct
16 Correct 188 ms 41788 KB Output is correct
17 Correct 192 ms 42476 KB Output is correct
18 Correct 207 ms 45612 KB Output is correct
19 Correct 78 ms 34320 KB Output is correct
20 Correct 188 ms 43244 KB Output is correct
21 Correct 189 ms 43256 KB Output is correct
22 Correct 193 ms 43812 KB Output is correct
23 Correct 205 ms 46896 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 4 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 29280 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 5 ms 29016 KB Output is correct
2 Correct 4 ms 29020 KB Output is correct
3 Correct 3 ms 29020 KB Output is correct
4 Correct 4 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 29280 KB Output is correct
8 Correct 4 ms 29276 KB Output is correct
9 Correct 65 ms 38088 KB Output is correct
10 Correct 84 ms 40136 KB Output is correct
11 Correct 83 ms 40124 KB Output is correct
12 Correct 106 ms 40784 KB Output is correct
13 Correct 91 ms 43988 KB Output is correct
14 Correct 79 ms 38344 KB Output is correct
15 Correct 199 ms 42108 KB Output is correct
16 Correct 188 ms 41788 KB Output is correct
17 Correct 192 ms 42476 KB Output is correct
18 Correct 207 ms 45612 KB Output is correct
19 Incorrect 169 ms 48884 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 -