oj.uz

Submission #392861

# Submission time Handle Problem Language Result Execution time Memory
392861 2021-04-22T03:20:32 Z wind_reaper Swapping Cities (APIO20_swap) C++17
6 / 100
 540 ms 41620 KB 
#include <bits/stdc++.h>

#ifndef LOCAL
#include "swap.h"
#endif

using namespace std;

// ******************** Constants ********************

const int MXN = 100000;
const int MXM = 200000;
const int MXS = 300000;
const int lg = 20;
int nxtnode = 0;

// ******************** global variables ********************

vector<int> g[MXS];

// ******************** LCA ********************

int up[lg][MXS], tin[MXS], tout[MXS], timer = 0;

void dfs(int node, int par){
	tin[node] = timer++;

	up[0][node] = par;
	for(int i = 1; i < lg; i++)
		up[i][node] = up[i-1][up[i-1][node]];

	for(int v : g[node]){
		if(v == par)
			continue;
		dfs(v, node);
	}

	tout[node] = timer;
}

inline bool isAncestor(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v){
	if(isAncestor(u, v))
		return u;
	if(isAncestor(v, u))
		return v;

	for(int i = lg-1; i >= 0; --i)
		if(!isAncestor(up[i][u], v))
			u = up[i][u];

	return up[0][u];
}

// ******************** KRT ********************

vector<bool> has(MXS);
int par[MXS], val[MXS];

void init(){
	for(int i = 0; i < MXS; i++)
		par[i] = i;
}

int get(int x){
	return (par[x] == x ? x : par[x] = get(par[x]));
}

void unite(int u, int v, int w){
	u = get(u), v = get(v);

	if(u == v){
		g[nxtnode].push_back(u);
		par[u] = nxtnode;
		has[nxtnode] = 1;
		val[nxtnode] = w;

		nxtnode++;
		return;
	}

	g[nxtnode].push_back(u);
	g[nxtnode].push_back(v);
	has[nxtnode] = has[u] | has[v];
	val[nxtnode] = w;
	par[u] = par[v] = nxtnode;

	nxtnode++;
	return;
}

int minup(int node){
	for(int i = lg-1; i >= 0; --i)
		if(has[up[i][node]] == 0)
			node = up[i][node];

	if(has[up[0][node]] == 0) return -1;
	return up[0][node];
}

// ******************** ********************

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
	vector<array<int, 3>> edges(M);
	for(int i = 0; i < M; i++)
		edges[i] = {W[i], U[i], V[i]};

	nxtnode = N;

	init();

	sort(edges.begin(), edges.end());

	for(auto& [w, u, v] : edges){
		unite(u, v, w);
	}

	dfs(nxtnode-1, nxtnode-1);
}

int getMinimumFuelCapacity(int X, int Y){
	int Z = lca(X, Y);
	int W = minup(Z);
	if(W == -1) return -1;
	return val[W];
}

#ifdef LOCAL
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int N, M;
	cin >> N >> M;

	vector<int> U(M), V(M), W(M);
	for(int i = 0; i < M; i++)
		cin >> U[i] >> V[i] >> W[i];

	init(N, M, U, V, W);

	int Q;
	cin >> Q;
	while(Q--){
		int X, Y;
		cin >> X >> Y;
		cout << getMinimumFuelCapacity(X, Y) << '\n';
	}	
	
	return 0; 
}
#endif

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8676 KB Output is correct
2 Correct 6 ms 8652 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8748 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 7 ms 8908 KB Output is correct
7 Correct 7 ms 8960 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 140 ms 29380 KB Output is correct
10 Correct 155 ms 33992 KB Output is correct
11 Correct 150 ms 33572 KB Output is correct
12 Correct 163 ms 35044 KB Output is correct
13 Correct 128 ms 37404 KB Output is correct
14 Correct 163 ms 29636 KB Output is correct
15 Correct 375 ms 37996 KB Output is correct
16 Correct 471 ms 37276 KB Output is correct
17 Correct 404 ms 39000 KB Output is correct
18 Correct 514 ms 41284 KB Output is correct
19 Correct 148 ms 17728 KB Output is correct
20 Correct 395 ms 38220 KB Output is correct
21 Correct 411 ms 37644 KB Output is correct
22 Correct 398 ms 39356 KB Output is correct
23 Correct 540 ms 41620 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8676 KB Output is correct
2 Correct 6 ms 8652 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8748 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 7 ms 8908 KB Output is correct
7 Correct 7 ms 8960 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 6 ms 8680 KB Output is correct
10 Incorrect 6 ms 8852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8680 KB Output is correct
2 Correct 6 ms 8676 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8652 KB Output is correct
5 Correct 6 ms 8748 KB Output is correct
6 Correct 7 ms 8908 KB Output is correct
7 Correct 7 ms 8908 KB Output is correct
8 Correct 7 ms 8960 KB Output is correct
9 Correct 7 ms 8908 KB Output is correct
10 Correct 140 ms 29380 KB Output is correct
11 Correct 155 ms 33992 KB Output is correct
12 Correct 150 ms 33572 KB Output is correct
13 Correct 163 ms 35044 KB Output is correct
14 Correct 128 ms 37404 KB Output is correct
15 Incorrect 6 ms 8852 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8676 KB Output is correct
2 Correct 6 ms 8652 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8748 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 7 ms 8908 KB Output is correct
7 Correct 7 ms 8960 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 140 ms 29380 KB Output is correct
10 Correct 155 ms 33992 KB Output is correct
11 Correct 150 ms 33572 KB Output is correct
12 Correct 163 ms 35044 KB Output is correct
13 Correct 128 ms 37404 KB Output is correct
14 Correct 163 ms 29636 KB Output is correct
15 Correct 375 ms 37996 KB Output is correct
16 Correct 471 ms 37276 KB Output is correct
17 Correct 404 ms 39000 KB Output is correct
18 Correct 514 ms 41284 KB Output is correct
19 Incorrect 523 ms 41264 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8680 KB Output is correct
2 Correct 6 ms 8676 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8652 KB Output is correct
5 Correct 6 ms 8748 KB Output is correct
6 Correct 7 ms 8908 KB Output is correct
7 Correct 7 ms 8908 KB Output is correct
8 Correct 7 ms 8960 KB Output is correct
9 Correct 7 ms 8908 KB Output is correct
10 Correct 140 ms 29380 KB Output is correct
11 Correct 155 ms 33992 KB Output is correct
12 Correct 150 ms 33572 KB Output is correct
13 Correct 163 ms 35044 KB Output is correct
14 Correct 128 ms 37404 KB Output is correct
15 Correct 163 ms 29636 KB Output is correct
16 Correct 375 ms 37996 KB Output is correct
17 Correct 471 ms 37276 KB Output is correct
18 Correct 404 ms 39000 KB Output is correct
19 Correct 514 ms 41284 KB Output is correct
20 Incorrect 523 ms 41264 KB Output isn't correct
21 Halted 0 ms 0 KB -