oj.uz

Submission #966873

# Submission time Handle Problem Language Result Execution time Memory
966873 2024-04-20T14:03:14 Z penguin133 Swapping Cities (APIO20_swap) C++17
13 / 100
 259 ms 39652 KB 
#include <bits/stdc++.h>
using namespace std;
#include "swap.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
vector <int> waiting[200005];
int par[200005], val[200005], deg[200005], good[200005], up[20][200005], dep[200005];
int cnt = 1;
pi adj[200005];
int getr(int x){return par[x] == x ? x : par[x] = getr(par[x]);}
void merge(int a, int b, int c){
	a = getr(a); b = getr(b);
	if(a == b)return;
	par[a] = par[b] = up[0][a] = up[0][b] = par[cnt];
	val[cnt] = c;
	adj[cnt] = {a, b};
	good[cnt] = 1;
	cnt++;
}
 
int par2[200005];
int g2(int x){return par2[x] == x ? x : par2[x] = g2(par2[x]);}
void m2(int a, int b){par2[g2(b)] = g2(a);}
 
void dfs(int x, int d){
	//cout << x << '\n';
	dep[x] = d;
	if(adj[x].fi == adj[x].se)return;
	dfs(adj[x].fi, d + 1);
	dfs(adj[x].se, d + 1);
}
 
int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int df = dep[v] -dep[u];
	for(int i = 0; i <= 19; i++)if(df >> i & 1)v = up[i][v];
	if(u ==v )return u;
	for(int i = 19; i >=0 ; i--)if(up[i][u] != up[i][v])u = up[i][u], v = up[i][v];
	return up[0][u];
}
 
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	vector <pii> bb;
	cnt = N;
	for(int i = 0; i < 2 * N; i++)par[i] = par2[i] = i;
	for(int i = 0; i < M; i++)bb.push_back({W[i], {U[i], V[i]}});
	sort(bb.begin(), bb.end());
	for(auto i : bb){
		int a = i.se.fi, b = i.se.se, w = i.fi;
		if(g2(a) == g2(b)){
			good[getr(a)] = 1;
			good[getr(b)] = 1;
			queue <int> q;
			q.push(a);
			q.push(b);
			merge(a, b, w);
			while(!q.empty()){
				int x = q.front(); q.pop();
				vector <int> aa = waiting[x];
				waiting[x].clear();
				for(auto j : aa){
				    if(getr(j) != getr(x)){
				       merge(x, j, w);
    			        q.push(j);
    			    }
				}
			}
		}
		else{
			m2(a, b);
			if(getr(a) != a || getr(b) != b)merge(a, b, w);
			else{
				deg[a]++; deg[b]++;
				if(max(deg[a], deg[b]) >= 3){
					good[getr(a)] = good[getr(b)] = 1;
					
					queue <int> q;
					q.push(a);
					q.push(b);
					merge(a, b, w);
					while(!q.empty()){
						int x = q.front(); q.pop();
						vector <int> aa = waiting[x];
						waiting[x].clear();
						for(auto j : aa){
						    if(getr(j) != getr(x)){
						        merge(x, j, w);
						        q.push(j);
						    }
						}
					}
				}
				else waiting[a].push_back(b), waiting[b].push_back(a);
			}
		}
	}
	for(int i = cnt - 1; i >= N; i--)if(!dep[i])dfs(i, 1);
	for(int i = 1; i <= 19; i++)for(int j = 0; j < 2 * N; j++)up[i][j] = up[i - 1][up[i - 1][j]];
}
 
int getMinimumFuelCapacity(int X, int Y) {
  if(getr(X) != getr(Y))return -1;
  //cout << lca(X, Y) << ' ';
  return val[lca(X, Y)];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22620 KB Output is correct
2 Correct 4 ms 22620 KB Output is correct
3 Correct 4 ms 22620 KB Output is correct
4 Correct 4 ms 22620 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22872 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 43 ms 31524 KB Output is correct
10 Correct 69 ms 32964 KB Output is correct
11 Correct 49 ms 32880 KB Output is correct
12 Correct 51 ms 33220 KB Output is correct
13 Correct 53 ms 33552 KB Output is correct
14 Correct 52 ms 31720 KB Output is correct
15 Correct 103 ms 35756 KB Output is correct
16 Correct 91 ms 35524 KB Output is correct
17 Correct 99 ms 36116 KB Output is correct
18 Correct 93 ms 36220 KB Output is correct
19 Correct 73 ms 32520 KB Output is correct
20 Correct 221 ms 39144 KB Output is correct
21 Correct 204 ms 39108 KB Output is correct
22 Correct 259 ms 39652 KB Output is correct
23 Correct 241 ms 39604 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22620 KB Output is correct
2 Correct 4 ms 22620 KB Output is correct
3 Correct 166 ms 35852 KB Output is correct
4 Correct 212 ms 35860 KB Output is correct
5 Correct 189 ms 36080 KB Output is correct
6 Correct 206 ms 35844 KB Output is correct
7 Correct 194 ms 35940 KB Output is correct
8 Correct 176 ms 35876 KB Output is correct
9 Correct 198 ms 36040 KB Output is correct
10 Correct 179 ms 35808 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22620 KB Output is correct
2 Correct 4 ms 22620 KB Output is correct
3 Correct 4 ms 22620 KB Output is correct
4 Correct 4 ms 22620 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22872 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 4 ms 26716 KB Output is correct
10 Incorrect 5 ms 26972 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26716 KB Output is correct
2 Correct 5 ms 22620 KB Output is correct
3 Correct 4 ms 22620 KB Output is correct
4 Correct 4 ms 22620 KB Output is correct
5 Correct 4 ms 22620 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22872 KB Output is correct
8 Correct 4 ms 22876 KB Output is correct
9 Correct 5 ms 22876 KB Output is correct
10 Correct 43 ms 31524 KB Output is correct
11 Correct 69 ms 32964 KB Output is correct
12 Correct 49 ms 32880 KB Output is correct
13 Correct 51 ms 33220 KB Output is correct
14 Correct 53 ms 33552 KB Output is correct
15 Incorrect 5 ms 26972 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 22620 KB Output is correct
2 Correct 4 ms 22620 KB Output is correct
3 Correct 4 ms 22620 KB Output is correct
4 Correct 4 ms 22620 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22872 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 43 ms 31524 KB Output is correct
10 Correct 69 ms 32964 KB Output is correct
11 Correct 49 ms 32880 KB Output is correct
12 Correct 51 ms 33220 KB Output is correct
13 Correct 53 ms 33552 KB Output is correct
14 Correct 52 ms 31720 KB Output is correct
15 Correct 103 ms 35756 KB Output is correct
16 Correct 91 ms 35524 KB Output is correct
17 Correct 99 ms 36116 KB Output is correct
18 Correct 93 ms 36220 KB Output is correct
19 Correct 166 ms 35852 KB Output is correct
20 Correct 212 ms 35860 KB Output is correct
21 Correct 189 ms 36080 KB Output is correct
22 Correct 206 ms 35844 KB Output is correct
23 Correct 194 ms 35940 KB Output is correct
24 Correct 176 ms 35876 KB Output is correct
25 Correct 198 ms 36040 KB Output is correct
26 Correct 179 ms 35808 KB Output is correct
27 Incorrect 5 ms 26972 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26716 KB Output is correct
2 Correct 5 ms 22620 KB Output is correct
3 Correct 4 ms 22620 KB Output is correct
4 Correct 4 ms 22620 KB Output is correct
5 Correct 4 ms 22620 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22872 KB Output is correct
8 Correct 4 ms 22876 KB Output is correct
9 Correct 5 ms 22876 KB Output is correct
10 Correct 43 ms 31524 KB Output is correct
11 Correct 69 ms 32964 KB Output is correct
12 Correct 49 ms 32880 KB Output is correct
13 Correct 51 ms 33220 KB Output is correct
14 Correct 53 ms 33552 KB Output is correct
15 Correct 52 ms 31720 KB Output is correct
16 Correct 103 ms 35756 KB Output is correct
17 Correct 91 ms 35524 KB Output is correct
18 Correct 99 ms 36116 KB Output is correct
19 Correct 93 ms 36220 KB Output is correct
20 Correct 166 ms 35852 KB Output is correct
21 Correct 212 ms 35860 KB Output is correct
22 Correct 189 ms 36080 KB Output is correct
23 Correct 206 ms 35844 KB Output is correct
24 Correct 194 ms 35940 KB Output is correct
25 Correct 176 ms 35876 KB Output is correct
26 Correct 198 ms 36040 KB Output is correct
27 Correct 179 ms 35808 KB Output is correct
28 Incorrect 5 ms 26972 KB Output isn't correct
29 Halted 0 ms 0 KB -