oj.uz

Submission #892049

# Submission time Handle Problem Language Result Execution time Memory
892049 2023-12-24T18:06:43 Z omeganot Swapping Cities (APIO20_swap) C++11
7 / 100
 2000 ms 42964 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];

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10880 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10880 KB Output is correct
9 Correct 79 ms 33940 KB Output is correct
10 Correct 99 ms 37440 KB Output is correct
11 Correct 115 ms 36816 KB Output is correct
12 Correct 107 ms 37848 KB Output is correct
13 Correct 112 ms 39136 KB Output is correct
14 Correct 91 ms 33620 KB Output is correct
15 Correct 349 ms 41124 KB Output is correct
16 Correct 356 ms 39528 KB Output is correct
17 Correct 351 ms 42964 KB Output is correct
18 Correct 382 ms 42068 KB Output is correct
19 Execution timed out 2037 ms 18688 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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 148 ms 37672 KB Output is correct
4 Correct 151 ms 37936 KB Output is correct
5 Correct 153 ms 38032 KB Output is correct
6 Correct 153 ms 37796 KB Output is correct
7 Correct 153 ms 38072 KB Output is correct
8 Correct 155 ms 37636 KB Output is correct
9 Correct 204 ms 37920 KB Output is correct
10 Correct 146 ms 37652 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10880 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10880 KB Output is correct
10 Correct 79 ms 33940 KB Output is correct
11 Correct 99 ms 37440 KB Output is correct
12 Correct 115 ms 36816 KB Output is correct
13 Correct 107 ms 37848 KB Output is correct
14 Correct 112 ms 39136 KB Output is correct
15 Correct 2 ms 10840 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10860 KB Output is correct
19 Correct 2 ms 10860 KB Output is correct
20 Incorrect 2 ms 11100 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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10880 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10880 KB Output is correct
9 Correct 79 ms 33940 KB Output is correct
10 Correct 99 ms 37440 KB Output is correct
11 Correct 115 ms 36816 KB Output is correct
12 Correct 107 ms 37848 KB Output is correct
13 Correct 112 ms 39136 KB Output is correct
14 Correct 91 ms 33620 KB Output is correct
15 Correct 349 ms 41124 KB Output is correct
16 Correct 356 ms 39528 KB Output is correct
17 Correct 351 ms 42964 KB Output is correct
18 Correct 382 ms 42068 KB Output is correct
19 Correct 148 ms 37672 KB Output is correct
20 Correct 151 ms 37936 KB Output is correct
21 Correct 153 ms 38032 KB Output is correct
22 Correct 153 ms 37796 KB Output is correct
23 Correct 153 ms 38072 KB Output is correct
24 Correct 155 ms 37636 KB Output is correct
25 Correct 204 ms 37920 KB Output is correct
26 Correct 146 ms 37652 KB Output is correct
27 Correct 2 ms 10840 KB Output is correct
28 Correct 2 ms 10844 KB Output is correct
29 Correct 2 ms 10844 KB Output is correct
30 Correct 2 ms 10860 KB Output is correct
31 Correct 2 ms 10860 KB Output is correct
32 Incorrect 2 ms 11100 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10880 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10880 KB Output is correct
10 Correct 79 ms 33940 KB Output is correct
11 Correct 99 ms 37440 KB Output is correct
12 Correct 115 ms 36816 KB Output is correct
13 Correct 107 ms 37848 KB Output is correct
14 Correct 112 ms 39136 KB Output is correct
15 Correct 91 ms 33620 KB Output is correct
16 Correct 349 ms 41124 KB Output is correct
17 Correct 356 ms 39528 KB Output is correct
18 Correct 351 ms 42964 KB Output is correct
19 Correct 382 ms 42068 KB Output is correct
20 Correct 148 ms 37672 KB Output is correct
21 Correct 151 ms 37936 KB Output is correct
22 Correct 153 ms 38032 KB Output is correct
23 Correct 153 ms 37796 KB Output is correct
24 Correct 153 ms 38072 KB Output is correct
25 Correct 155 ms 37636 KB Output is correct
26 Correct 204 ms 37920 KB Output is correct
27 Correct 146 ms 37652 KB Output is correct
28 Correct 2 ms 10840 KB Output is correct
29 Correct 2 ms 10844 KB Output is correct
30 Correct 2 ms 10844 KB Output is correct
31 Correct 2 ms 10860 KB Output is correct
32 Correct 2 ms 10860 KB Output is correct
33 Incorrect 2 ms 11100 KB Output isn't correct
34 Halted 0 ms 0 KB -