oj.uz

답안 #871319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871319 2023-11-10T14:39:25 Z serifefedartar 자매 도시 (APIO20_swap) C++17
6 / 100
 233 ms 53356 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]) {
		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 29116 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 ms 29132 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 29316 KB Output is correct
9 Correct 68 ms 40440 KB Output is correct
10 Correct 89 ms 42692 KB Output is correct
11 Correct 83 ms 42716 KB Output is correct
12 Correct 86 ms 43464 KB Output is correct
13 Correct 77 ms 46556 KB Output is correct
14 Correct 75 ms 40644 KB Output is correct
15 Correct 178 ms 46928 KB Output is correct
16 Correct 175 ms 46772 KB Output is correct
17 Correct 218 ms 47488 KB Output is correct
18 Correct 198 ms 50580 KB Output is correct
19 Correct 79 ms 36376 KB Output is correct
20 Correct 213 ms 47944 KB Output is correct
21 Correct 179 ms 47908 KB Output is correct
22 Correct 190 ms 48836 KB Output is correct
23 Correct 233 ms 52036 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 161 ms 53356 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 29116 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 ms 29132 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 29316 KB Output is correct
9 Incorrect 3 ms 29184 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 29184 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 29116 KB Output is correct
4 Correct 3 ms 29020 KB Output is correct
5 Correct 4 ms 29132 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 29316 KB Output is correct
9 Correct 68 ms 40440 KB Output is correct
10 Correct 89 ms 42692 KB Output is correct
11 Correct 83 ms 42716 KB Output is correct
12 Correct 86 ms 43464 KB Output is correct
13 Correct 77 ms 46556 KB Output is correct
14 Correct 75 ms 40644 KB Output is correct
15 Correct 178 ms 46928 KB Output is correct
16 Correct 175 ms 46772 KB Output is correct
17 Correct 218 ms 47488 KB Output is correct
18 Correct 198 ms 50580 KB Output is correct
19 Incorrect 161 ms 53356 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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