oj.uz

답안 #499296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499296 2021-12-27T21:05:55 Z sidon 자매 도시 (APIO20_swap) C++17
6 / 100
 439 ms 49852 KB 
#include <bits/stdc++.h>
using namespace std;
#include "swap.h"

const int Z = 1e5, B = 18, INF = 2e9;

array<int, B> p[Z], q[Z], r[Z];
vector<int> e(Z, -1), d(Z);
vector<array<int, 2>> g[Z];
set<array<int, 2>> s[Z];

int find(int u) {
	return e[u] < 0 ? u : e[u] = find(e[u]);
}

void dfs_0(int u) {
	for(auto &[v, w] : g[u]) if(v != p[u][0]) {
		p[v][0] = u, q[v][0] = w, d[v] = d[u] + 1;
		dfs_0(v);

		if(size(s[u]) < size(s[v]))
			s[u].swap(s[v]);

		for(auto &i : s[v])
			if(s[u].find(i) == end(s[u]))
				s[u].insert(i);
			else
				s[u].erase(i);
	}

	if(!empty(s[u])) r[u][0] = (*begin(s[u]))[0];
}

void dfs_1(int u) {
	for(int i = 1; i < B; i++) {
		p[u][i] = p[p[u][i-1]][i-1];
		q[u][i] = max(q[u][i-1], q[p[u][i-1]][i-1]);
		r[u][i] = min(r[u][i-1], r[p[u][i-1]][i-1]);
	}
	for(auto &[v, w] : g[u]) if(v != p[u][0])
		dfs_1(v);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	array<int, 3> h[M];
	for(int i = 0; i < M; i++) {
		h[i] = {W[i], U[i], V[i]};
	}
	sort(h, h+M);
	for(int i = 0; i < M; i++) {
		int u = find(h[i][1]), v = find(h[i][2]), w = h[i][0];
		if(u == v)
			for(int k : {1, 2})
				s[h[i][k]].insert({w, i});
		else {
			if(e[u] > e[v]) swap(u, v);
			e[u] += e[v], e[v] = u;
			for(int k : {1, 2})
				g[h[i][k]].push_back({h[i][3-k], w});
		}
	}

	for(int u = 0; u < N; u++)
		for(int &i : r[u]) i = INF;

	dfs_0(0), dfs_1(0);
}

int getMinimumFuelCapacity(int X, int Y) {
	int u = X, v = Y, qV = 0, rV = INF;

	if(d[u] > d[v]) swap(u, v);
	for(int i = 0; i < B; i++) {
		if((d[v] - d[u]) & (1<<i)) {
			qV = max(qV, q[v][i]);
			rV = min(rV, r[v][i]);
			v = p[v][i];
		}
	}
	if(u != v) {	
		for(int i = B; --i; ) {
			if(p[u][i] != p[v][i]) {
				qV = max({qV, q[u][i], q[v][i]});
				rV = min({rV, r[u][i], r[v][i]});
				u = p[u][i];
				v = p[v][i];
			}
		}
		qV = max({qV, q[u][0], q[v][0]});
		rV = min({rV, r[u][0], r[v][0]});
	}
	return rV == INF ? -1 : max(rV, qV);
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8268 KB Output is correct
5 Correct 4 ms 8396 KB Output is correct
6 Correct 4 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 4 ms 8464 KB Output is correct
9 Correct 120 ms 35968 KB Output is correct
10 Correct 155 ms 44300 KB Output is correct
11 Correct 143 ms 42896 KB Output is correct
12 Correct 153 ms 45416 KB Output is correct
13 Correct 148 ms 48224 KB Output is correct
14 Correct 146 ms 34968 KB Output is correct
15 Correct 357 ms 45744 KB Output is correct
16 Correct 397 ms 42352 KB Output is correct
17 Correct 331 ms 49852 KB Output is correct
18 Correct 390 ms 47692 KB Output is correct
19 Correct 85 ms 17880 KB Output is correct
20 Correct 439 ms 45924 KB Output is correct
21 Correct 370 ms 43488 KB Output is correct
22 Correct 390 ms 47632 KB Output is correct
23 Correct 361 ms 48452 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8268 KB Output is correct
5 Correct 4 ms 8396 KB Output is correct
6 Correct 4 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 4 ms 8464 KB Output is correct
9 Correct 4 ms 8140 KB Output is correct
10 Incorrect 4 ms 8396 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 4 ms 8268 KB Output is correct
6 Correct 4 ms 8396 KB Output is correct
7 Correct 4 ms 8396 KB Output is correct
8 Correct 5 ms 8396 KB Output is correct
9 Correct 4 ms 8464 KB Output is correct
10 Correct 120 ms 35968 KB Output is correct
11 Correct 155 ms 44300 KB Output is correct
12 Correct 143 ms 42896 KB Output is correct
13 Correct 153 ms 45416 KB Output is correct
14 Correct 148 ms 48224 KB Output is correct
15 Incorrect 4 ms 8396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8268 KB Output is correct
5 Correct 4 ms 8396 KB Output is correct
6 Correct 4 ms 8396 KB Output is correct
7 Correct 5 ms 8396 KB Output is correct
8 Correct 4 ms 8464 KB Output is correct
9 Correct 120 ms 35968 KB Output is correct
10 Correct 155 ms 44300 KB Output is correct
11 Correct 143 ms 42896 KB Output is correct
12 Correct 153 ms 45416 KB Output is correct
13 Correct 148 ms 48224 KB Output is correct
14 Correct 146 ms 34968 KB Output is correct
15 Correct 357 ms 45744 KB Output is correct
16 Correct 397 ms 42352 KB Output is correct
17 Correct 331 ms 49852 KB Output is correct
18 Correct 390 ms 47692 KB Output is correct
19 Incorrect 182 ms 36732 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 4 ms 8268 KB Output is correct
6 Correct 4 ms 8396 KB Output is correct
7 Correct 4 ms 8396 KB Output is correct
8 Correct 5 ms 8396 KB Output is correct
9 Correct 4 ms 8464 KB Output is correct
10 Correct 120 ms 35968 KB Output is correct
11 Correct 155 ms 44300 KB Output is correct
12 Correct 143 ms 42896 KB Output is correct
13 Correct 153 ms 45416 KB Output is correct
14 Correct 148 ms 48224 KB Output is correct
15 Correct 146 ms 34968 KB Output is correct
16 Correct 357 ms 45744 KB Output is correct
17 Correct 397 ms 42352 KB Output is correct
18 Correct 331 ms 49852 KB Output is correct
19 Correct 390 ms 47692 KB Output is correct
20 Incorrect 182 ms 36732 KB Output isn't correct
21 Halted 0 ms 0 KB -