oj.uz

답안 #657003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657003 2022-11-08T17:12:50 Z 600Mihnea 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 14100 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9 + 7;
vector<int> edge_ids;
vector<int> papa_dsu;
vector<int> wait_outside;
vector<int> par;
vector<int> dep;
vector<int> weight_up;
vector<int> oth_min;
vector<vector<pair<int, int>>> g;
bool deja = 0;

int get_root(int a) {
	if (papa_dsu[a] == a) {
		return a;
	} else {
		return papa_dsu[a] = get_root(papa_dsu[a]);
	}
}

void dfs(int a, int p = -1) {
	par[a] = p;
	vector<pair<int, int>> kids;
	for (auto &it : g[a]) {		
		int b = it.first;
		if (b == p) {
			continue;
		}
		weight_up[b] = it.second;
		dep[b] = 1 + dep[a];
		dfs(b, a);
		kids.push_back(it);
	}
	g[a] = kids;
	int mn = INF;
	for (int rev = 0; rev < 2; rev++) {
		for (auto &it : g[a]) {
			int b = it.first;
			oth_min[b] = min(oth_min[b], mn);
			mn = min(mn, weight_up[b]);
		}
		reverse(g[a].begin(), g[a].end());
	}
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
	par.resize(n, -1);
	dep.resize(n, 0);
	weight_up.resize(n, INF);
	oth_min.resize(n, INF);
	assert(deja == 0);
	deja = 1;
	assert((int) U.size() == m);
	assert((int) V.size() == m);
	assert((int) W.size() == m);
	
	g.resize(n);
	
	edge_ids.resize(m);
	iota(edge_ids.begin(), edge_ids.end(), 0);
		
	sort(edge_ids.begin(), edge_ids.end(), [&] (int i, int j) {
		return W[i] < W[j];
	});

		
	papa_dsu.resize(n);
	iota(papa_dsu.begin(), papa_dsu.end(), 0);
		
	wait_outside.resize(n, INF);
	
	for (int j = 0; j < m; j++) {
		int index = edge_ids[j];
		int a = U[index];
		int b = V[index];
		assert(0 <= a && a < n);
		assert(0 <= b && b < n);
		if (get_root(a) != get_root(b)) {
			g[a].push_back({b, W[index]});
			g[b].push_back({a, W[index]});
			papa_dsu[get_root(a)] = get_root(b);
		} else {
			wait_outside[a] = min(wait_outside[a], W[index]);
			wait_outside[b] = min(wait_outside[b], W[index]);
		}
	}
	
	dfs(0);
}

int lca_dumb(int x, int y) {
	while (x != y) {
		if (dep[x] > dep[y]) {
			swap(x, y);	
		}
		// dep[x] <= dep[y];
		y = par[y];
	}
	return x;
}

int iq = 0;

int getMinimumFuelCapacity(int x, int y) {
	iq++;
	if (x == y) {
		return 0;	
	}
	int z = lca_dumb(x, y);

	bool init_good = (x != z && y != z);

	int ix = x;
	int iy = y;
	int sol = 0, sol2 = INF;
	sol2 = min(sol2, wait_outside[x]);
	sol2 = min(sol2, wait_outside[y]);
//	cout << par[x] << " " << par[y] << "\n";
	while (x != y) {
		if (dep[x] < dep[y]) {
			swap(x, y);
		}
		//cout << " = " << x << " " << y << "\n";
		assert(dep[x] >= dep[y]);
		// cobor x
		if (par[x] != x) {
			sol = max(sol, weight_up[x]);
		}
		if (par[x] != z) {	
			sol2 = min(sol2, oth_min[x]);
		}
		x = par[x];
		sol2 = min(sol2, wait_outside[x]);
	}
	if (init_good) {
		sol2 = min(sol2, weight_up[z]);
		while (par[ix] != z) {
			ix = par[ix];
		}
		while (par[iy] != z) {
			iy = par[iy];
		}
		for (auto &it : g[z]) {
			int b = it.first;
			if (b == ix || b == iy) {
				continue;
			}
			sol2 = min(sol2, weight_up[b]);
		}
	}	
	if (sol2 == INF) {
		return -1;
	}
	return max(sol, sol2);
	//cout << " = " << ix << " " << iy << "\n";
	cout << sol << "\n";
	cout << sol2 << "\n";
	exit(0);
  return max(sol, sol2);
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 2066 ms 14100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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