oj.uz

Submission #392863

# Submission time Handle Problem Language Result Execution time Memory
392863 2021-04-22T03:50:15 Z wind_reaper Swapping Cities (APIO20_swap) C++17
13 / 100
 556 ms 43440 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], degree[MXN];

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){
	degree[u]++;
	degree[v]++;

	has[nxtnode] = (degree[u] >= 3 || degree[v] >= 3);

	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);
	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];

	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);
	Z = minup(Z);
	if(Z == -1) return -1;
	return val[Z];
}

#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 8652 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 8780 KB Output is correct
5 Correct 7 ms 8952 KB Output is correct
6 Correct 6 ms 8908 KB Output is correct
7 Correct 7 ms 8908 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 123 ms 28996 KB Output is correct
10 Correct 151 ms 33344 KB Output is correct
11 Correct 148 ms 32928 KB Output is correct
12 Correct 160 ms 34512 KB Output is correct
13 Correct 126 ms 36748 KB Output is correct
14 Correct 142 ms 29124 KB Output is correct
15 Correct 392 ms 35044 KB Output is correct
16 Correct 431 ms 34372 KB Output is correct
17 Correct 386 ms 35932 KB Output is correct
18 Correct 456 ms 38212 KB Output is correct
19 Correct 156 ms 16832 KB Output is correct
20 Correct 378 ms 35416 KB Output is correct
21 Correct 387 ms 34820 KB Output is correct
22 Correct 390 ms 36372 KB Output is correct
23 Correct 556 ms 38616 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8652 KB Output is correct
2 Correct 6 ms 8652 KB Output is correct
3 Correct 483 ms 39464 KB Output is correct
4 Correct 499 ms 43440 KB Output is correct
5 Correct 516 ms 42876 KB Output is correct
6 Correct 525 ms 43332 KB Output is correct
7 Correct 483 ms 43228 KB Output is correct
8 Correct 510 ms 42088 KB Output is correct
9 Correct 460 ms 42836 KB Output is correct
10 Correct 466 ms 41856 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8652 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 8780 KB Output is correct
5 Correct 7 ms 8952 KB Output is correct
6 Correct 6 ms 8908 KB Output is correct
7 Correct 7 ms 8908 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 5 ms 8704 KB Output is correct
10 Correct 6 ms 8908 KB Output is correct
11 Incorrect 6 ms 8908 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8704 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 8652 KB Output is correct
5 Correct 6 ms 8780 KB Output is correct
6 Correct 7 ms 8952 KB Output is correct
7 Correct 6 ms 8908 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 7 ms 8908 KB Output is correct
10 Correct 123 ms 28996 KB Output is correct
11 Correct 151 ms 33344 KB Output is correct
12 Correct 148 ms 32928 KB Output is correct
13 Correct 160 ms 34512 KB Output is correct
14 Correct 126 ms 36748 KB Output is correct
15 Correct 6 ms 8908 KB Output is correct
16 Incorrect 6 ms 8908 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8652 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 8780 KB Output is correct
5 Correct 7 ms 8952 KB Output is correct
6 Correct 6 ms 8908 KB Output is correct
7 Correct 7 ms 8908 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 123 ms 28996 KB Output is correct
10 Correct 151 ms 33344 KB Output is correct
11 Correct 148 ms 32928 KB Output is correct
12 Correct 160 ms 34512 KB Output is correct
13 Correct 126 ms 36748 KB Output is correct
14 Correct 142 ms 29124 KB Output is correct
15 Correct 392 ms 35044 KB Output is correct
16 Correct 431 ms 34372 KB Output is correct
17 Correct 386 ms 35932 KB Output is correct
18 Correct 456 ms 38212 KB Output is correct
19 Correct 483 ms 39464 KB Output is correct
20 Correct 499 ms 43440 KB Output is correct
21 Correct 516 ms 42876 KB Output is correct
22 Correct 525 ms 43332 KB Output is correct
23 Correct 483 ms 43228 KB Output is correct
24 Correct 510 ms 42088 KB Output is correct
25 Correct 460 ms 42836 KB Output is correct
26 Correct 466 ms 41856 KB Output is correct
27 Correct 6 ms 8908 KB Output is correct
28 Incorrect 6 ms 8908 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8704 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 8652 KB Output is correct
5 Correct 6 ms 8780 KB Output is correct
6 Correct 7 ms 8952 KB Output is correct
7 Correct 6 ms 8908 KB Output is correct
8 Correct 7 ms 8908 KB Output is correct
9 Correct 7 ms 8908 KB Output is correct
10 Correct 123 ms 28996 KB Output is correct
11 Correct 151 ms 33344 KB Output is correct
12 Correct 148 ms 32928 KB Output is correct
13 Correct 160 ms 34512 KB Output is correct
14 Correct 126 ms 36748 KB Output is correct
15 Correct 142 ms 29124 KB Output is correct
16 Correct 392 ms 35044 KB Output is correct
17 Correct 431 ms 34372 KB Output is correct
18 Correct 386 ms 35932 KB Output is correct
19 Correct 456 ms 38212 KB Output is correct
20 Correct 483 ms 39464 KB Output is correct
21 Correct 499 ms 43440 KB Output is correct
22 Correct 516 ms 42876 KB Output is correct
23 Correct 525 ms 43332 KB Output is correct
24 Correct 483 ms 43228 KB Output is correct
25 Correct 510 ms 42088 KB Output is correct
26 Correct 460 ms 42836 KB Output is correct
27 Correct 466 ms 41856 KB Output is correct
28 Correct 6 ms 8908 KB Output is correct
29 Incorrect 6 ms 8908 KB Output isn't correct
30 Halted 0 ms 0 KB -