oj.uz

답안 #871322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871322 2023-11-10T14:51:32 Z serifefedartar 자매 도시 (APIO20_swap) C++17
6 / 100
 221 ms 49528 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 = 22; 
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);
	
  	deg[old_u]++, deg[old_v]++;
	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]) {
		if (u == up[0][node])
			continue;
		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 + M; 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 29020 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 29016 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 3 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 3 ms 29276 KB Output is correct
9 Correct 74 ms 38616 KB Output is correct
10 Correct 87 ms 40860 KB Output is correct
11 Correct 92 ms 40732 KB Output is correct
12 Correct 86 ms 41156 KB Output is correct
13 Correct 79 ms 44304 KB Output is correct
14 Correct 81 ms 38904 KB Output is correct
15 Correct 173 ms 42808 KB Output is correct
16 Correct 209 ms 42404 KB Output is correct
17 Correct 218 ms 43076 KB Output is correct
18 Correct 208 ms 46144 KB Output is correct
19 Correct 81 ms 34572 KB Output is correct
20 Correct 197 ms 43964 KB Output is correct
21 Correct 204 ms 43652 KB Output is correct
22 Correct 221 ms 44584 KB Output is correct
23 Correct 201 ms 47488 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 29020 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 29016 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 3 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 3 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 3 ms 29020 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 29016 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 3 ms 29276 KB Output is correct
7 Correct 4 ms 29276 KB Output is correct
8 Correct 3 ms 29276 KB Output is correct
9 Correct 74 ms 38616 KB Output is correct
10 Correct 87 ms 40860 KB Output is correct
11 Correct 92 ms 40732 KB Output is correct
12 Correct 86 ms 41156 KB Output is correct
13 Correct 79 ms 44304 KB Output is correct
14 Correct 81 ms 38904 KB Output is correct
15 Correct 173 ms 42808 KB Output is correct
16 Correct 209 ms 42404 KB Output is correct
17 Correct 218 ms 43076 KB Output is correct
18 Correct 208 ms 46144 KB Output is correct
19 Incorrect 157 ms 49528 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 -