oj.uz

Submission #788048

# Submission time Handle Problem Language Result Execution time Memory
788048 2023-07-19T16:56:41 Z ToniB Swapping Cities (APIO20_swap) C++17
6 / 100
 113 ms 19176 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 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 63 ms 13620 KB Output is correct
10 Correct 76 ms 15524 KB Output is correct
11 Correct 57 ms 15316 KB Output is correct
12 Correct 66 ms 15872 KB Output is correct
13 Correct 53 ms 15972 KB Output is correct
14 Correct 49 ms 13712 KB Output is correct
15 Correct 104 ms 17352 KB Output is correct
16 Correct 98 ms 17120 KB Output is correct
17 Correct 104 ms 17644 KB Output is correct
18 Correct 103 ms 17640 KB Output is correct
19 Correct 45 ms 10176 KB Output is correct
20 Correct 96 ms 18552 KB Output is correct
21 Correct 104 ms 18424 KB Output is correct
22 Correct 113 ms 19176 KB Output is correct
23 Correct 104 ms 19140 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 88 ms 19008 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Incorrect 2 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 2 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 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 63 ms 13620 KB Output is correct
10 Correct 76 ms 15524 KB Output is correct
11 Correct 57 ms 15316 KB Output is correct
12 Correct 66 ms 15872 KB Output is correct
13 Correct 53 ms 15972 KB Output is correct
14 Correct 49 ms 13712 KB Output is correct
15 Correct 104 ms 17352 KB Output is correct
16 Correct 98 ms 17120 KB Output is correct
17 Correct 104 ms 17644 KB Output is correct
18 Correct 103 ms 17640 KB Output is correct
19 Incorrect 88 ms 19008 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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