제출 #892049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892049		omeganot	자매 도시 (APIO20_swap)	C++11	7 / 100	2037 ms	42964 KiB

swap

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;

const int MAX = 1E5;
const int LOG = 17;

int timer = -1;
int depth[MAX];
int tin[MAX]; int tout[MAX];
int lift[MAX][LOG];
int lift2[MAX][LOG];
int lift3[MAX][LOG];
vector<array<int, 2>> adj[MAX];

struct DSU {
	int n;
	vector<int> parent;
	DSU(int n) {
		this->n = n;
		parent.assign(n, -1);
	}
	int find(int x) {
		if(parent[x] < 0) {
			return x;
		}
		parent[x] = find(parent[x]);
		return parent[x];
	}
	void unite(int x, int y) {
		int px = find(x); int py = find(y);
		if(px == py) {
			return;
		}
		if(parent[px] > parent[py]) {
			swap(px, py);
		}
		parent[px] += parent[py];
		parent[py] = px;
	}
	bool sameSet(int x, int y) {
		return find(x) == find(y);
	}
};

int n; int m;
vector<array<int, 3>> edges;
vector<bool> spanning;

void dfs(int x, int p, int pw) {
	lift[x][0] = p;
	lift2[x][0] = pw;
	tin[x] = ++timer;
	lift3[x][0] = INF + 1;
	if(p != -1) {
		for(array<int, 2> i : adj[p]) {
			if(i[1] != lift[p][0] && i[1] != x) {
				lift3[x][0] = i[0];
				break;
			}
		}
	}
	for(array<int, 2> i : adj[x]) {
		if(i[1] != p) {
			depth[i[1]] = depth[x] + 1;
			dfs(i[1], x, i[0]);
		}
	}
	tout[x] = timer;
}

bool isAncestor(int x, int y) {
	return tin[x] <= tin[y] && tout[x] >= tin[y];
}

int jump(int x, int y) {
	for(int i = 0; i < LOG; i++) {
		if(y & (1 << i)) {
			x = lift[x][i];
		}
	}
	return x;
}

int lca(int x, int y) {
	if(depth[x] > depth[y]) {
		swap(x, y);
	}
	y = jump(y, depth[y] - depth[x]);
	if(x == y) {
		return x;
	}
	for(int i = LOG - 1; i >= 0; i--) {
		if(lift[x][i] != lift[y][i]) {
			x = lift[x][i]; 
			y = lift[y][i];
		}
	}
	return lift[x][0];
}

int getMax(int x, int y) {
	int ans = 0;
	for(int i = 0; i < LOG; i++) {
		if(y & (1 << i)) {
			ans = max(ans, lift2[x][i]);
			x = lift[x][i];
		}
	}
	return ans;
}

int getMin(int x, int y) {
	int ans = INF + 1;
	for(int i = 0; i < LOG; i++) {
		if(y & (1 << i)) {
			ans = min(ans, lift3[x][i]);
			x = lift[x][i];
		}
	}
	return ans;
}

int getMinimumFuelCapacity(int X, int Y) {
	int z = lca(X, Y);
	int pathMax = 0;
	if(X != z) {
		pathMax = getMax(X, depth[X] - depth[z]);
	}
	if(Y != z) {
		pathMax = max(pathMax, getMax(Y, depth[Y] - depth[z]));
	}
	int minExtraEdge = INF + 1;
	if(z != X && z != Y) {
		for(array<int, 2> i : adj[z]) {
			if(!isAncestor(i[1], X) && !isAncestor(i[1], Y)) {
				minExtraEdge = i[0];
				break;
			}
		}
	} else {
		int cnt = 0;
		for(array<int, 2> i : adj[z]) {
			if(!isAncestor(i[1], X) && !isAncestor(i[1], Y)) {
				cnt++;
				if(cnt >= 2) {
					minExtraEdge = i[0];
					break;
				}
			}
		}
	}
	if(X != z) {
		int cnt = 0;
		for(array<int, 2> i : adj[X]) {
			if(i[1] != lift[X][0]) {
				cnt++;
				if(cnt >= 2) {
					minExtraEdge = min(minExtraEdge, i[0]);
					break;
				}
			}
		}
		if(lift[X][0] != z) {
			minExtraEdge = min(minExtraEdge, getMin(X, depth[X] - depth[z] - 1));
		}
	}
	if(Y != z) {
		int cnt = 0;
		for(array<int, 2> i : adj[Y]) {
			if(i[1] != lift[Y][0]) {
				cnt++;
				if(cnt >= 2) {
					minExtraEdge = min(minExtraEdge, i[0]);
					break;
				}
			}
		}
		if(lift[Y][0] != z) {
			minExtraEdge = min(minExtraEdge, getMin(Y, depth[Y] - depth[z] - 1));
		}
	}
	if(m >= n) {
		DSU dsu(n);
		int lastWeight = INF + 1;
		for(int i = 0; i < m; i++) {
			if(spanning[i] && isAncestor(z, edges[i][1]) && isAncestor(z, edges[i][2]) && ((isAncestor(edges[i][1], X) && isAncestor(edges[i][2], X)) || (isAncestor(edges[i][1], Y) && isAncestor(edges[i][2], Y)))) {
				continue;
			}
			dsu.unite(edges[i][1], edges[i][2]);
			lastWeight = edges[i][0];
			if(dsu.sameSet(X, Y)) {
				break;
			}
		}
		minExtraEdge = min(minExtraEdge, lastWeight);
	}
	int ans = max(minExtraEdge, pathMax);
	return (ans <= INF ? ans : -1);

}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N; m = M;
	edges.resize(M);
	spanning.resize(M);
	for(int i = 0; i < M; i++) {
		edges[i] = {W[i], U[i], V[i]};
	}
	sort(edges.begin(), edges.end());
	DSU dsu(N);
	for(int i = 0; i < M; i++) {
		if(!dsu.sameSet(edges[i][1], edges[i][2])) {
			adj[edges[i][1]].push_back({edges[i][0], edges[i][2]});
			adj[edges[i][2]].push_back({edges[i][0], edges[i][1]});
			dsu.unite(edges[i][1], edges[i][2]);
			spanning[i] = true;
		}
	}
	for(int i = 0; i < N; i++) {
		sort(adj[i].begin(), adj[i].end());
	}
	dfs(0, -1, -1);
	for(int i = 1; i < LOG; i++) {
		for(int j = 0; j < N; j++) {
			if(lift[j][i - 1] == -1) {
				lift[j][i] = -1;
			} else {
				lift[j][i] = lift[lift[j][i - 1]][i - 1];
				lift2[j][i] = max(lift2[j][i - 1], lift2[lift[j][i - 1]][i - 1]);
				lift3[j][i] = min(lift3[j][i - 1], lift3[lift[j][i - 1]][i - 1]);
			}
		}
	} 
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27