oj.uz

Submission #892069

# Submission time Handle Problem Language Result Execution time Memory
892069 2023-12-24T18:15:37 Z omeganot Swapping Cities (APIO20_swap) C++11
7 / 100
 2000 ms 44368 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)) {
				minExtraEdge = i[0];
				break;
			}
		}
	} else {
		int cnt = 0;
		for(array<int, 2> i : adj2[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 : 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 85 ms 37024 KB Output is correct
10 Correct 112 ms 40732 KB Output is correct
11 Correct 118 ms 40080 KB Output is correct
12 Correct 126 ms 41192 KB Output is correct
13 Correct 112 ms 42580 KB Output is correct
14 Correct 96 ms 36616 KB Output is correct
15 Correct 335 ms 41976 KB Output is correct
16 Correct 334 ms 40304 KB Output is correct
17 Correct 311 ms 44368 KB Output is correct
18 Correct 332 ms 43056 KB Output is correct
19 Execution timed out 2060 ms 19540 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 171 ms 40304 KB Output is correct
4 Correct 176 ms 40804 KB Output is correct
5 Correct 168 ms 40692 KB Output is correct
6 Correct 166 ms 40768 KB Output is correct
7 Correct 165 ms 40684 KB Output is correct
8 Correct 158 ms 40308 KB Output is correct
9 Correct 198 ms 40520 KB Output is correct
10 Correct 158 ms 40068 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12916 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 3 ms 12980 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Incorrect 2 ms 12888 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 85 ms 37024 KB Output is correct
11 Correct 112 ms 40732 KB Output is correct
12 Correct 118 ms 40080 KB Output is correct
13 Correct 126 ms 41192 KB Output is correct
14 Correct 112 ms 42580 KB Output is correct
15 Correct 2 ms 12916 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12980 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 2 ms 12892 KB Output is correct
20 Incorrect 2 ms 12888 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 85 ms 37024 KB Output is correct
10 Correct 112 ms 40732 KB Output is correct
11 Correct 118 ms 40080 KB Output is correct
12 Correct 126 ms 41192 KB Output is correct
13 Correct 112 ms 42580 KB Output is correct
14 Correct 96 ms 36616 KB Output is correct
15 Correct 335 ms 41976 KB Output is correct
16 Correct 334 ms 40304 KB Output is correct
17 Correct 311 ms 44368 KB Output is correct
18 Correct 332 ms 43056 KB Output is correct
19 Correct 171 ms 40304 KB Output is correct
20 Correct 176 ms 40804 KB Output is correct
21 Correct 168 ms 40692 KB Output is correct
22 Correct 166 ms 40768 KB Output is correct
23 Correct 165 ms 40684 KB Output is correct
24 Correct 158 ms 40308 KB Output is correct
25 Correct 198 ms 40520 KB Output is correct
26 Correct 158 ms 40068 KB Output is correct
27 Correct 2 ms 12916 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12980 KB Output is correct
30 Correct 2 ms 12892 KB Output is correct
31 Correct 2 ms 12892 KB Output is correct
32 Incorrect 2 ms 12888 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 85 ms 37024 KB Output is correct
11 Correct 112 ms 40732 KB Output is correct
12 Correct 118 ms 40080 KB Output is correct
13 Correct 126 ms 41192 KB Output is correct
14 Correct 112 ms 42580 KB Output is correct
15 Correct 96 ms 36616 KB Output is correct
16 Correct 335 ms 41976 KB Output is correct
17 Correct 334 ms 40304 KB Output is correct
18 Correct 311 ms 44368 KB Output is correct
19 Correct 332 ms 43056 KB Output is correct
20 Correct 171 ms 40304 KB Output is correct
21 Correct 176 ms 40804 KB Output is correct
22 Correct 168 ms 40692 KB Output is correct
23 Correct 166 ms 40768 KB Output is correct
24 Correct 165 ms 40684 KB Output is correct
25 Correct 158 ms 40308 KB Output is correct
26 Correct 198 ms 40520 KB Output is correct
27 Correct 158 ms 40068 KB Output is correct
28 Correct 2 ms 12916 KB Output is correct
29 Correct 2 ms 12892 KB Output is correct
30 Correct 3 ms 12980 KB Output is correct
31 Correct 2 ms 12892 KB Output is correct
32 Correct 2 ms 12892 KB Output is correct
33 Incorrect 2 ms 12888 KB Output isn't correct
34 Halted 0 ms 0 KB -