oj.uz

답안 #892072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
892072 2023-12-24T18:18:04 Z omeganot 자매 도시 (APIO20_swap) C++11
7 / 100
 2000 ms 44112 KB 
#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];
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;
	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]);
		}
	}
	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 : adj2[z]) {
			if((!isAncestor(i[1], X) && !isAncestor(i[1], Y)) || depth[i[1]] < depth[z]) {
				minExtraEdge = i[0];
				break;
			}
		}
	} else {
		int cnt = 0;
		for(array<int, 2> i : adj2[z]) {
			if((!isAncestor(i[1], X) && !isAncestor(i[1], Y)) || depth[i[1]] < depth[z]) {
				cnt++;
				if(cnt >= 2) {
					minExtraEdge = i[0];
					break;
				}
			}
		}
	}
	if(X != z) {
		int cnt = 0;
		for(array<int, 2> i : adj2[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 : adj2[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]};
		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);
	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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 116 ms 37032 KB Output is correct
10 Correct 132 ms 40660 KB Output is correct
11 Correct 129 ms 40104 KB Output is correct
12 Correct 143 ms 41044 KB Output is correct
13 Correct 122 ms 42368 KB Output is correct
14 Correct 165 ms 36728 KB Output is correct
15 Correct 432 ms 42064 KB Output is correct
16 Correct 519 ms 40396 KB Output is correct
17 Correct 487 ms 44112 KB Output is correct
18 Correct 471 ms 42992 KB Output is correct
19 Execution timed out 2041 ms 19284 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 200 ms 40184 KB Output is correct
4 Correct 215 ms 40748 KB Output is correct
5 Correct 239 ms 40656 KB Output is correct
6 Correct 225 ms 40748 KB Output is correct
7 Correct 209 ms 40676 KB Output is correct
8 Correct 242 ms 40180 KB Output is correct
9 Correct 200 ms 40520 KB Output is correct
10 Correct 222 ms 40068 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Incorrect 2 ms 12980 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 116 ms 37032 KB Output is correct
11 Correct 132 ms 40660 KB Output is correct
12 Correct 129 ms 40104 KB Output is correct
13 Correct 143 ms 41044 KB Output is correct
14 Correct 122 ms 42368 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 2 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Incorrect 2 ms 12980 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 116 ms 37032 KB Output is correct
10 Correct 132 ms 40660 KB Output is correct
11 Correct 129 ms 40104 KB Output is correct
12 Correct 143 ms 41044 KB Output is correct
13 Correct 122 ms 42368 KB Output is correct
14 Correct 165 ms 36728 KB Output is correct
15 Correct 432 ms 42064 KB Output is correct
16 Correct 519 ms 40396 KB Output is correct
17 Correct 487 ms 44112 KB Output is correct
18 Correct 471 ms 42992 KB Output is correct
19 Correct 200 ms 40184 KB Output is correct
20 Correct 215 ms 40748 KB Output is correct
21 Correct 239 ms 40656 KB Output is correct
22 Correct 225 ms 40748 KB Output is correct
23 Correct 209 ms 40676 KB Output is correct
24 Correct 242 ms 40180 KB Output is correct
25 Correct 200 ms 40520 KB Output is correct
26 Correct 222 ms 40068 KB Output is correct
27 Correct 2 ms 12892 KB Output is correct
28 Correct 3 ms 12892 KB Output is correct
29 Correct 2 ms 12892 KB Output is correct
30 Correct 4 ms 12892 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Incorrect 2 ms 12980 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 116 ms 37032 KB Output is correct
11 Correct 132 ms 40660 KB Output is correct
12 Correct 129 ms 40104 KB Output is correct
13 Correct 143 ms 41044 KB Output is correct
14 Correct 122 ms 42368 KB Output is correct
15 Correct 165 ms 36728 KB Output is correct
16 Correct 432 ms 42064 KB Output is correct
17 Correct 519 ms 40396 KB Output is correct
18 Correct 487 ms 44112 KB Output is correct
19 Correct 471 ms 42992 KB Output is correct
20 Correct 200 ms 40184 KB Output is correct
21 Correct 215 ms 40748 KB Output is correct
22 Correct 239 ms 40656 KB Output is correct
23 Correct 225 ms 40748 KB Output is correct
24 Correct 209 ms 40676 KB Output is correct
25 Correct 242 ms 40180 KB Output is correct
26 Correct 200 ms 40520 KB Output is correct
27 Correct 222 ms 40068 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 2 ms 12892 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Incorrect 2 ms 12980 KB Output isn't correct
34 Halted 0 ms 0 KB -