oj.uz

Submission #392862

# Submission time Handle Problem Language Result Execution time Memory
392862 2021-04-22T03:29:17 Z wind_reaper Swapping Cities (APIO20_swap) C++17
6 / 100
 534 ms 37440 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){
	if(has[node] == 1)
		return node;

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

	assert(node == nxtnode-1 || has[node] == 0);

	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 8660 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 8784 KB Output is correct
5 Correct 6 ms 8800 KB Output is correct
6 Correct 8 ms 8816 KB Output is correct
7 Correct 6 ms 8912 KB Output is correct
8 Correct 6 ms 8908 KB Output is correct
9 Correct 121 ms 27644 KB Output is correct
10 Correct 154 ms 31988 KB Output is correct
11 Correct 154 ms 31540 KB Output is correct
12 Correct 156 ms 32880 KB Output is correct
13 Correct 121 ms 35268 KB Output is correct
14 Correct 144 ms 27780 KB Output is correct
15 Correct 380 ms 33612 KB Output is correct
16 Correct 375 ms 33028 KB Output is correct
17 Correct 374 ms 34396 KB Output is correct
18 Correct 479 ms 36740 KB Output is correct
19 Correct 137 ms 15756 KB Output is correct
20 Correct 382 ms 34024 KB Output is correct
21 Correct 384 ms 33328 KB Output is correct
22 Correct 394 ms 34872 KB Output is correct
23 Correct 492 ms 37268 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8660 KB Output is correct
2 Correct 6 ms 8652 KB Output is correct
3 Incorrect 534 ms 37440 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 8660 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 8784 KB Output is correct
5 Correct 6 ms 8800 KB Output is correct
6 Correct 8 ms 8816 KB Output is correct
7 Correct 6 ms 8912 KB Output is correct
8 Correct 6 ms 8908 KB Output is correct
9 Correct 7 ms 8652 KB Output is correct
10 Incorrect 6 ms 8908 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8652 KB Output is correct
2 Correct 6 ms 8660 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 8784 KB Output is correct
6 Correct 6 ms 8800 KB Output is correct
7 Correct 8 ms 8816 KB Output is correct
8 Correct 6 ms 8912 KB Output is correct
9 Correct 6 ms 8908 KB Output is correct
10 Correct 121 ms 27644 KB Output is correct
11 Correct 154 ms 31988 KB Output is correct
12 Correct 154 ms 31540 KB Output is correct
13 Correct 156 ms 32880 KB Output is correct
14 Correct 121 ms 35268 KB Output is correct
15 Incorrect 6 ms 8908 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 8660 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 8784 KB Output is correct
5 Correct 6 ms 8800 KB Output is correct
6 Correct 8 ms 8816 KB Output is correct
7 Correct 6 ms 8912 KB Output is correct
8 Correct 6 ms 8908 KB Output is correct
9 Correct 121 ms 27644 KB Output is correct
10 Correct 154 ms 31988 KB Output is correct
11 Correct 154 ms 31540 KB Output is correct
12 Correct 156 ms 32880 KB Output is correct
13 Correct 121 ms 35268 KB Output is correct
14 Correct 144 ms 27780 KB Output is correct
15 Correct 380 ms 33612 KB Output is correct
16 Correct 375 ms 33028 KB Output is correct
17 Correct 374 ms 34396 KB Output is correct
18 Correct 479 ms 36740 KB Output is correct
19 Incorrect 534 ms 37440 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8652 KB Output is correct
2 Correct 6 ms 8660 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 8784 KB Output is correct
6 Correct 6 ms 8800 KB Output is correct
7 Correct 8 ms 8816 KB Output is correct
8 Correct 6 ms 8912 KB Output is correct
9 Correct 6 ms 8908 KB Output is correct
10 Correct 121 ms 27644 KB Output is correct
11 Correct 154 ms 31988 KB Output is correct
12 Correct 154 ms 31540 KB Output is correct
13 Correct 156 ms 32880 KB Output is correct
14 Correct 121 ms 35268 KB Output is correct
15 Correct 144 ms 27780 KB Output is correct
16 Correct 380 ms 33612 KB Output is correct
17 Correct 375 ms 33028 KB Output is correct
18 Correct 374 ms 34396 KB Output is correct
19 Correct 479 ms 36740 KB Output is correct
20 Incorrect 534 ms 37440 KB Output isn't correct
21 Halted 0 ms 0 KB -