oj.uz

Submission #788038

# Submission time Handle Problem Language Result Execution time Memory
788038 2023-07-19T16:48:27 Z ToniB Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 38264 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){
	if(uf[x] == -1) return x;
	return uf[x] = f(uf[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 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){
			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){
	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:37:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   37 |   if(dep[u] - dep[v] & 1 << i){
      |      ~~~~~~~^~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 6 ms 7636 KB Output is correct
6 Correct 6 ms 7580 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 6 ms 7728 KB Output is correct
9 Execution timed out 2077 ms 35340 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Execution timed out 2076 ms 38264 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 6 ms 7636 KB Output is correct
6 Correct 6 ms 7580 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 6 ms 7728 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Incorrect 6 ms 7628 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7408 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 6 ms 7636 KB Output is correct
7 Correct 6 ms 7580 KB Output is correct
8 Correct 6 ms 7636 KB Output is correct
9 Correct 6 ms 7728 KB Output is correct
10 Execution timed out 2077 ms 35340 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 6 ms 7636 KB Output is correct
6 Correct 6 ms 7580 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 6 ms 7728 KB Output is correct
9 Execution timed out 2077 ms 35340 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7408 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 6 ms 7636 KB Output is correct
7 Correct 6 ms 7580 KB Output is correct
8 Correct 6 ms 7636 KB Output is correct
9 Correct 6 ms 7728 KB Output is correct
10 Execution timed out 2077 ms 35340 KB Time limit exceeded
11 Halted 0 ms 0 KB -