oj.uz

Submission #964718

# Submission time Handle Problem Language Result Execution time Memory
964718 2024-04-17T11:55:16 Z socpite Swapping Cities (APIO20_swap) C++14
6 / 100
 72 ms 16332 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, m;
int Wmax;

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;
	m = M;
	Wmax = *max_element(W.begin(), W.end());
}

int getMinimumFuelCapacity(int a, int b) {
	if(n == m)return Wmax;
	return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6852 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 20 ms 10076 KB Output is correct
10 Correct 25 ms 10844 KB Output is correct
11 Correct 22 ms 10768 KB Output is correct
12 Correct 24 ms 10832 KB Output is correct
13 Correct 23 ms 10844 KB Output is correct
14 Correct 22 ms 10332 KB Output is correct
15 Correct 67 ms 15096 KB Output is correct
16 Correct 61 ms 14932 KB Output is correct
17 Correct 64 ms 15032 KB Output is correct
18 Correct 63 ms 15040 KB Output is correct
19 Correct 38 ms 12300 KB Output is correct
20 Correct 60 ms 15976 KB Output is correct
21 Correct 64 ms 16140 KB Output is correct
22 Correct 67 ms 16332 KB Output is correct
23 Correct 72 ms 16308 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6852 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Incorrect 2 ms 6492 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6852 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 20 ms 10076 KB Output is correct
10 Correct 25 ms 10844 KB Output is correct
11 Correct 22 ms 10768 KB Output is correct
12 Correct 24 ms 10832 KB Output is correct
13 Correct 23 ms 10844 KB Output is correct
14 Correct 22 ms 10332 KB Output is correct
15 Correct 67 ms 15096 KB Output is correct
16 Correct 61 ms 14932 KB Output is correct
17 Correct 64 ms 15032 KB Output is correct
18 Correct 63 ms 15040 KB Output is correct
19 Incorrect 68 ms 14268 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -