oj.uz

Submission #788047

# Submission time Handle Problem Language Result Execution time Memory
788047 2023-07-19T16:56:06 Z ToniB Swapping Cities (APIO20_swap) C++17
6 / 100
 113 ms 20016 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<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);
		cycle[v] = edge;
		uf_bio[v] = 1;
	}
	if(sz[u] > sz[v]) swap(u, v);
	sz[v] += sz[u];
	uf[u] = v;
}

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;
		cycle[node] = 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;
	}
	
	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});
//		}
//	}
//	
//	for(int i = 0; i < n; ++i){
//		int node = i;
//		while(node != -1 && !uf_bio[node]){
//			node = uf[node];
//		}
//		if(node != -1) cycle[i] = cycle[node];
//	}
//	
//	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;
	return edges[m - 1].X;
	if(min(cycle[x], cycle[y]) == 0) 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:35:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |   if(dep[u] - dep[v] & 1 << i){
      |      ~~~~~~~^~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 36 ms 11644 KB Output is correct
10 Correct 61 ms 12676 KB Output is correct
11 Correct 44 ms 12600 KB Output is correct
12 Correct 52 ms 12924 KB Output is correct
13 Correct 61 ms 12800 KB Output is correct
14 Correct 43 ms 11884 KB Output is correct
15 Correct 97 ms 14408 KB Output is correct
16 Correct 87 ms 14268 KB Output is correct
17 Correct 88 ms 14580 KB Output is correct
18 Correct 113 ms 14652 KB Output is correct
19 Correct 43 ms 10012 KB Output is correct
20 Correct 87 ms 19328 KB Output is correct
21 Correct 109 ms 19416 KB Output is correct
22 Correct 95 ms 19972 KB Output is correct
23 Correct 95 ms 20016 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 91 ms 14792 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 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Incorrect 3 ms 4948 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 4948 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 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 36 ms 11644 KB Output is correct
10 Correct 61 ms 12676 KB Output is correct
11 Correct 44 ms 12600 KB Output is correct
12 Correct 52 ms 12924 KB Output is correct
13 Correct 61 ms 12800 KB Output is correct
14 Correct 43 ms 11884 KB Output is correct
15 Correct 97 ms 14408 KB Output is correct
16 Correct 87 ms 14268 KB Output is correct
17 Correct 88 ms 14580 KB Output is correct
18 Correct 113 ms 14652 KB Output is correct
19 Incorrect 91 ms 14792 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 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -