oj.uz

답안 #871057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871057 2023-11-09T19:31:33 Z serifefedartar 자매 도시 (APIO20_swap) C++17
0 / 100
 397 ms 524288 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[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; 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
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 25044 KB Output is correct
4 Runtime error 397 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Runtime error 385 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 25044 KB Output is correct
4 Runtime error 397 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 25044 KB Output is correct
4 Runtime error 397 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 25044 KB Output is correct
4 Runtime error 397 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 25044 KB Output is correct
4 Runtime error 397 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -