oj.uz

답안 #788034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788034 2023-07-19T16:43:30 Z ToniB 자매 도시 (APIO20_swap) C++17
0 / 100
 69 ms 11444 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){
	if(x == y) return 0;
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7292 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 22 ms 9184 KB Output is correct
10 Correct 27 ms 9524 KB Output is correct
11 Correct 26 ms 9496 KB Output is correct
12 Correct 27 ms 9696 KB Output is correct
13 Correct 27 ms 9676 KB Output is correct
14 Correct 25 ms 9308 KB Output is correct
15 Correct 68 ms 11356 KB Output is correct
16 Correct 68 ms 11352 KB Output is correct
17 Correct 69 ms 11404 KB Output is correct
18 Correct 69 ms 11444 KB Output is correct
19 Incorrect 41 ms 9976 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Incorrect 63 ms 11188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7292 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 4 ms 7252 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7292 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 22 ms 9184 KB Output is correct
10 Correct 27 ms 9524 KB Output is correct
11 Correct 26 ms 9496 KB Output is correct
12 Correct 27 ms 9696 KB Output is correct
13 Correct 27 ms 9676 KB Output is correct
14 Correct 25 ms 9308 KB Output is correct
15 Correct 68 ms 11356 KB Output is correct
16 Correct 68 ms 11352 KB Output is correct
17 Correct 69 ms 11404 KB Output is correct
18 Correct 69 ms 11444 KB Output is correct
19 Incorrect 63 ms 11188 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -