oj.uz

Submission #788033

# Submission time Handle Problem Language Result Execution time Memory
788033 2023-07-19T16:42:34 Z ToniB Swapping Cities (APIO20_swap) C++17
0 / 100
 75 ms 15920 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 2;
const int LOG = 18;

int n, m, cycle[MAXN], uf[MAXN], sz[MAXN], cnt[MAXN];
int dep[MAXN], bl[MAXN][LOG], bl_w[MAXN][LOG];
bool uf_bio[MAXN];
vector<int> nodes[MAXN];
vector<pair<int, int> > adj[MAXN], tree[MAXN];
vector<pair<int, pii> > edges;

int f(int x){
	while(uf[x] != -1) x = uf[x];
	return x;
}
void join(int u, int v, int edge){
	if(uf_bio[u] ^ uf_bio[v]){
		if(uf_bio[v]) swap(u, v);
		for(int x : nodes[v]) cycle[x] = edge;
		uf_bio[v] = 1;
	}
	if(sz[u] > sz[v]) swap(u, v);
	sz[v] += sz[u];
	uf[u] = v;
	for(int x : nodes[u]) nodes[v].push_back(x);
}
int lift(int node, int step){
	for(int i = 0; i < LOG; ++i){
		if(step & 1 << i) node = bl[node][i];
	}
	return node;
}
int calc(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	int ret = 0, lift = u;
	for(int i = 0; i < LOG; ++i){
		if(dep[u] - dep[v] & 1 << i){
			ret = max(ret, bl_w[lift][i]);
			lift = bl[lift][i];
		}
	}
	u = lift;

	if(u == v) return ret;

	for(int i = LOG - 1; i >= 0; --i){
		if(bl[u][i] != bl[v][i]){
			ret = max(ret, bl_w[u][i]);
			ret = max(ret, bl_w[v][i]);
			u = bl[u][i];
			v = bl[v][i];
		}
	}
	ret = max(ret, bl_w[u][0]);
	ret = max(ret, bl_w[v][0]);
	return ret;
}

void dfs(int node, int anc, int edge = 0){
	bl[node][0] = anc;
	bl_w[node][0] = edge;
	dep[node] = dep[anc] + 1;
	for(pii x : tree[node]){
		if(x.X == anc) continue;
		dfs(x.X, node, x.Y);
	}
}

void connect(int node, int edge){
	if(!uf_bio[node]){
		uf_bio[node] = 1;
		for(int x : nodes[node]) cycle[x] = edge;
	}
}

void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w){
//	n = _n; m = _m;
//	for(int i = 0; i < n; ++i){
//		uf[i] = -1; sz[i] = 1;
//		nodes[i] = {i};
//	}
//	
//	for(int i = 0; i < m; ++i){
//		adj[u[i]].push_back({v[i], w[i]});
//		adj[v[i]].push_back({u[i], w[i]});
//		edges.push_back({w[i], {u[i], v[i]}});
//	}
//
//	sort(edges.begin(), edges.end());
//
//	for(auto p : edges){
//		int u = p.Y.X, v = p.Y.Y;
//		++cnt[u]; ++cnt[v];
//		int fu = f(u), fv = f(v);
//		if(cnt[u] >= 3) connect(fu, p.X);
//		if(cnt[v] >= 3) connect(fv, p.X);
//		u = fu; v = fv;
//		if(u == v){
//			connect(u, p.X);
//		} else {
//			join(u, v, p.X);
//			tree[p.Y.X].push_back({p.Y.Y, p.X});
//			tree[p.Y.Y].push_back({p.Y.X, p.X});
//		}
//	}
//
//	dfs(0, 0);
//
//	for(int j = 1; j < n; ++j){
//		for(int i = 0; i < n; ++i){
//			assert(bl[i][j - 1] >= 0);
//			assert(bl[i][j - 1] < n);
//			bl[i][j] = bl[bl[i][j - 1]][j - 1];
//			bl_w[i][j] = max(bl_w[i][j - 1], bl_w[bl[i][j - 1]][j - 1]);
//		}
//	}
}
int getMinimumFuelCapacity(int x, int y){
	return -1;
	if(m + 1 == n) return -1;
	int val = calc(x, y);
	return max(val, min(cycle[x], cycle[y]));
}

Compilation message

swap.cpp: In function 'int calc(int, int)':
swap.cpp:42:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   42 |   if(dep[u] - dep[v] & 1 << i){
      |      ~~~~~~~^~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7312 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7356 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct
8 Correct 4 ms 7384 KB Output is correct
9 Correct 22 ms 9320 KB Output is correct
10 Correct 26 ms 11596 KB Output is correct
11 Correct 26 ms 11540 KB Output is correct
12 Correct 27 ms 11720 KB Output is correct
13 Correct 28 ms 11816 KB Output is correct
14 Correct 27 ms 11220 KB Output is correct
15 Correct 68 ms 15652 KB Output is correct
16 Correct 75 ms 15684 KB Output is correct
17 Correct 70 ms 15832 KB Output is correct
18 Correct 70 ms 15920 KB Output is correct
19 Incorrect 41 ms 11924 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Incorrect 63 ms 11364 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 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7312 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7356 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct
8 Correct 4 ms 7384 KB Output is correct
9 Incorrect 3 ms 7252 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7252 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 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 4 ms 7312 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7356 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct
8 Correct 4 ms 7384 KB Output is correct
9 Correct 22 ms 9320 KB Output is correct
10 Correct 26 ms 11596 KB Output is correct
11 Correct 26 ms 11540 KB Output is correct
12 Correct 27 ms 11720 KB Output is correct
13 Correct 28 ms 11816 KB Output is correct
14 Correct 27 ms 11220 KB Output is correct
15 Correct 68 ms 15652 KB Output is correct
16 Correct 75 ms 15684 KB Output is correct
17 Correct 70 ms 15832 KB Output is correct
18 Correct 70 ms 15920 KB Output is correct
19 Incorrect 63 ms 11364 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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