oj.uz

Submission #964498

# Submission time Handle Problem Language Result Execution time Memory
964498 2024-04-17T03:17:01 Z socpite Swapping Cities (APIO20_swap) C++14
0 / 100
 308 ms 67496 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5+5;
const int INF = 1e9+5;
const int lg = 18;

int n;

int sp[lg][maxn];
int sp_mx[lg][maxn], sp_mn[lg][maxn];
int dep[maxn];
int in_tree[maxn];

vector<pair<int, int>> g[maxn];
vector<pair<int, pair<int, int>>> E;

int up[maxn];

int Find(int x){
	return up[x] != -1 ? up[x] = Find(up[x]) : x;
}

bool Union(int a, int b){
	a = Find(a);
	b = Find(b);
	if(a == b)return false;
	up[a] = b;
	return true;
}

void dfs(int x, int p){
	sp_mn[0][x] = INF;
	sp[0][x] = p;
	for(auto v: g[x]){
		if(v.first == p)continue;
		dep[v.first] = dep[x] + 1;
		sp_mx[0][v.first] = v.second;
		dfs(v.first, x);
	}
}

void build(){
	for(int i = 1; i < lg; i++){
		for(int j = 0; j < n; j++){
			if(sp[i-1][j] == -1)sp[i][j] = -1;
			else {
				sp[i][j] = sp[i-1][sp[i-1][j]];
				sp_mx[i][j] = max(sp_mx[i-1][j], sp_mx[i-1][sp[i-1][j]]);
			}
			sp_mn[i][j] = INF;
		}
	}
}

void tup_upd(int &x, int dist, int w){
	for(int i = 0; i < lg; i++){
		if(dist&(1<<i)){
			sp_mn[i][x] = w;
			x = sp[i][x];
		}
	}
}

void upd_path(int a, int b, int w){
	if(dep[a] < dep[b])swap(a, b);
	tup_upd(a, dep[a] - dep[b], w);
	if(a == b)return;
	for(int i = lg-1; i >= 0; i--){
		if(sp[i][a] != sp[i][b]){
			sp_mn[i][a] = min(sp_mn[i][a], w);
			sp_mn[i][b] = min(sp_mn[i][b], w);
			a = sp[i][a];
			b = sp[i][b];
		}
	}
	sp_mn[0][a] = min(sp_mn[0][a], w);
	sp_mn[0][b] = min(sp_mn[0][b], w);
}

void push(){
	for(int i = lg-1; i > 0; i--){
		for(int j = 0; j < n; j++){
			if(sp[i][j] == -1)continue;
			sp_mn[i-1][j] = min(sp_mn[i-1][j], sp_mn[i][j]);
			sp_mn[i-1][sp[i-1][j]] = min(sp_mn[i-1][sp[i-1][j]], sp_mn[i][j]);
		}
	}
}

void tup_query(int &x, int dist, int &mx, int &mn){
	for(int i = 0; i < lg; i++){
		if(dist&(1<<i)){
			mn = min(sp_mn[i][x], mn);
			mx = max(sp_mx[i][x], mx);
			x = sp[i][x];
		}
	}
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	for(int i = 0; i < M; i++){
		E.push_back({W[i], {U[i], V[i]}});
	}
	for(int i = 0; i < N; i++)up[i] = -1;
	sort(E.begin(), E.end());
	for(int i = 0; i < M; i++){
		if(Union(E[i].second.first, E[i].second.second)){
			// cout << E[i].second.first << " " << E[i].second.second << endl
			g[E[i].second.first].push_back({E[i].second.second, E[i].first});
			g[E[i].second.second].push_back({E[i].second.first, E[i].first});
			in_tree[i] = 1;
		}
	}
	dfs(0, -1);
	build();
	for(int i = 0; i < M; i++){
		if(!in_tree[i])upd_path(E[i].second.first, E[i].second.second, E[i].first);
	}
	push();
}

int getMinimumFuelCapacity(int a, int b) {
	int mx = 0, mn = INF;
	if(dep[a] < dep[b])swap(a, b);
	tup_query(a, dep[a] - dep[b], mx, mn);
	if(a != b){
		for(int i = lg-1; i >= 0; i--){
			if(sp[i][a] != sp[i][b]){
				mn = min(sp_mn[i][a], mn);
				mn = min(sp_mn[i][b], mn);
				mx = max(sp_mx[i][a], mx);
				mx = min(sp_mx[i][b], mx);
				a = sp[i][a];
				b = sp[i][b];
			}
		}
		mn = min(sp_mn[0][a], mn);
		mn = min(sp_mn[0][b], mn);
		mx = max(mx, sp_mx[0][a]);
		mx = max(mx, sp_mx[0][b]);
	}

	if(max(mn, mx) == INF)return -1;
	return max(mn, mx);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 5 ms 35272 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 7 ms 41304 KB Output is correct
5 Correct 7 ms 43612 KB Output is correct
6 Correct 6 ms 43612 KB Output is correct
7 Correct 6 ms 43424 KB Output is correct
8 Correct 6 ms 43612 KB Output is correct
9 Correct 57 ms 58196 KB Output is correct
10 Correct 66 ms 61636 KB Output is correct
11 Correct 68 ms 60864 KB Output is correct
12 Correct 80 ms 62088 KB Output is correct
13 Correct 65 ms 63444 KB Output is correct
14 Correct 71 ms 57988 KB Output is correct
15 Correct 308 ms 65564 KB Output is correct
16 Correct 232 ms 64008 KB Output is correct
17 Correct 260 ms 67496 KB Output is correct
18 Correct 265 ms 66392 KB Output is correct
19 Incorrect 77 ms 52656 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 5 ms 35272 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 7 ms 41304 KB Output is correct
5 Correct 7 ms 43612 KB Output is correct
6 Correct 6 ms 43612 KB Output is correct
7 Correct 6 ms 43424 KB Output is correct
8 Correct 6 ms 43612 KB Output is correct
9 Correct 5 ms 35164 KB Output is correct
10 Incorrect 6 ms 39492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 5 ms 35164 KB Output is correct
3 Correct 5 ms 35272 KB Output is correct
4 Correct 6 ms 35164 KB Output is correct
5 Correct 7 ms 41304 KB Output is correct
6 Correct 7 ms 43612 KB Output is correct
7 Correct 6 ms 43612 KB Output is correct
8 Correct 6 ms 43424 KB Output is correct
9 Correct 6 ms 43612 KB Output is correct
10 Correct 57 ms 58196 KB Output is correct
11 Correct 66 ms 61636 KB Output is correct
12 Correct 68 ms 60864 KB Output is correct
13 Correct 80 ms 62088 KB Output is correct
14 Correct 65 ms 63444 KB Output is correct
15 Incorrect 6 ms 39492 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 5 ms 35272 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 7 ms 41304 KB Output is correct
5 Correct 7 ms 43612 KB Output is correct
6 Correct 6 ms 43612 KB Output is correct
7 Correct 6 ms 43424 KB Output is correct
8 Correct 6 ms 43612 KB Output is correct
9 Correct 57 ms 58196 KB Output is correct
10 Correct 66 ms 61636 KB Output is correct
11 Correct 68 ms 60864 KB Output is correct
12 Correct 80 ms 62088 KB Output is correct
13 Correct 65 ms 63444 KB Output is correct
14 Correct 71 ms 57988 KB Output is correct
15 Correct 308 ms 65564 KB Output is correct
16 Correct 232 ms 64008 KB Output is correct
17 Correct 260 ms 67496 KB Output is correct
18 Correct 265 ms 66392 KB Output is correct
19 Incorrect 98 ms 48740 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35164 KB Output is correct
2 Correct 5 ms 35164 KB Output is correct
3 Correct 5 ms 35272 KB Output is correct
4 Correct 6 ms 35164 KB Output is correct
5 Correct 7 ms 41304 KB Output is correct
6 Correct 7 ms 43612 KB Output is correct
7 Correct 6 ms 43612 KB Output is correct
8 Correct 6 ms 43424 KB Output is correct
9 Correct 6 ms 43612 KB Output is correct
10 Correct 57 ms 58196 KB Output is correct
11 Correct 66 ms 61636 KB Output is correct
12 Correct 68 ms 60864 KB Output is correct
13 Correct 80 ms 62088 KB Output is correct
14 Correct 65 ms 63444 KB Output is correct
15 Correct 71 ms 57988 KB Output is correct
16 Correct 308 ms 65564 KB Output is correct
17 Correct 232 ms 64008 KB Output is correct
18 Correct 260 ms 67496 KB Output is correct
19 Correct 265 ms 66392 KB Output is correct
20 Incorrect 98 ms 48740 KB Output isn't correct
21 Halted 0 ms 0 KB -