oj.uz

Submission #656993

# Submission time Handle Problem Language Result Execution time Memory
656993 2022-11-08T16:49:07 Z 600Mihnea Swapping Cities (APIO20_swap) C++17
0 / 100
 218 ms 17804 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, 0);
	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[edge_ids[i]] < W[edge_ids[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 getMinimumFuelCapacity(int x, int y) {
	int sol = 0, sol2 = INF;
	sol2 = min(sol2, wait_outside[x]);
	sol2 = min(sol2, wait_outside[y]);
	while (x != y) {
		if (dep[x] < dep[y]) {
			swap(x, y);
		}
		assert(dep[x] >= dep[y]);
		// cobor x
		sol = max(sol, weight_up[x]);
		x = par[x];
		sol2 = min(sol2, oth_min[x]);
		sol2 = min(sol2, wait_outside[x]);
	}	
	if (sol2 == INF) {
		return -1;
	}
  return max(sol, sol2);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 218 ms 17804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -