제출 #788034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788034		ToniB	자매 도시 (APIO20_swap)	C++17	0 / 100	69 ms	11444 KiB

swap

#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]));
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27