제출 #892086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892086		omeganot	자매 도시 (APIO20_swap)	C++11	7 / 100	2063 ms	65048 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];
int dp[MAX];
vector<int> dp2[MAX];
int ind[MAX];
vector<array<int, 2>> adj[MAX];
vector<array<int, 2>> adj2[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;
	dp[x] = INF + 1;
	if(p != -1) {
		for(array<int, 2> i : adj2[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]);
			dp[x] = min(dp[x], max(dp[i[1]], i[0]));
		}
	}
	tout[x] = timer;
	int cnt = 0;
	for(array<int, 2> i : adj2[x]) {
		if(i[1] != p) {
			cnt++;
			if(cnt >= 2) {
				dp[x] = min(dp[x], i[0]);
				break;
			}
		}
	}
}

void dfs2(int x, int p, int dpUp) {
	vector<array<int, 2>> vals;
	vals.push_back({dpUp, p});
	for(array<int, 2> i : adj[x]) {
		if(i[1] != p) {
			vals.push_back({dp[i[1]], i[1]});
		}
	}
	sort(vals.begin(), vals.end());
	dp2[x].resize(adj[x].size());
	for(int i = 0; i < adj[x].size(); i++) {
		if(adj[x][i][1] != p) {
			ind[adj[x][i][1]] = i;
			dp2[x][i] = INF + 1;
			for(int j = 0; j < vals.size(); j++) {
				if(vals[j][1] != adj[x][i][1]) {
					dp2[x][i] = vals[j][0];
					break;
				}
			}
			int cnt = 0;
			for(array<int, 2> j : adj[x]) {
				if(j[1] != adj[x][i][1]) {
					cnt++;
					if(cnt == 2) {	
						dp2[x][i] = min(dp2[x][i], j[0]);
						break;
					}
				}
			}
			dfs2(adj[x][i][1], x, max(dp2[x][i], adj[x][i][0]));
		}
	}

}

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 : adj2[z]) {
			if((!isAncestor(i[1], X) && !isAncestor(i[1], Y)) || depth[i[1]] < depth[z]) {
				minExtraEdge = i[0];
				break;
			}
		}
	} else {
		if(X == z) {
			int v = jump(Y, depth[Y] - depth[z] - 1);
			minExtraEdge = min(minExtraEdge, dp2[X][ind[v]]);
		} else {
			int v = jump(X, depth[X] - depth[z] - 1);
			minExtraEdge = min(minExtraEdge, dp2[Y][ind[v]]);
		}
	}
	if(X != z) {
		minExtraEdge = min(minExtraEdge, dp[X]);
		if(lift[X][0] != z) {
			minExtraEdge = min(minExtraEdge, getMin(X, depth[X] - depth[z] - 1));
		}
	}
	if(Y != z) {
		minExtraEdge = min(minExtraEdge, dp[Y]);
		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]};
		adj2[U[i]].push_back({W[i], V[i]});
		adj2[V[i]].push_back({W[i], U[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());
		sort(adj2[i].begin(), adj2[i].end());
	}
	dfs(0, -1, -1);
	dfs2(0, -1, INF + 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]);
			}
		}
	} 
}

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

swap.cpp: In function 'void dfs2(int, int, int)':
swap.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0; i < adj[x].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
swap.cpp:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    for(int j = 0; j < vals.size(); j++) {
      |                   ~~^~~~~~~~~~~~~

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