oj.uz

Submission #892087

# Submission time Handle Problem Language Result Execution time Memory
892087 2023-12-24T18:56:55 Z omeganot Swapping Cities (APIO20_swap) C++11
67 / 100
 2000 ms 65028 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];
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({max(dp[i[1]], i[0]), 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]);
			}
		}
	} 
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 5 ms 17496 KB Output is correct
8 Correct 4 ms 17244 KB Output is correct
9 Correct 121 ms 48216 KB Output is correct
10 Correct 148 ms 55636 KB Output is correct
11 Correct 150 ms 54608 KB Output is correct
12 Correct 180 ms 56912 KB Output is correct
13 Correct 151 ms 61180 KB Output is correct
14 Correct 141 ms 47368 KB Output is correct
15 Correct 366 ms 57180 KB Output is correct
16 Correct 411 ms 52880 KB Output is correct
17 Correct 370 ms 62492 KB Output is correct
18 Correct 398 ms 59472 KB Output is correct
19 Execution timed out 2063 ms 25940 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 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 176 ms 46684 KB Output is correct
4 Correct 204 ms 47472 KB Output is correct
5 Correct 202 ms 47228 KB Output is correct
6 Correct 201 ms 47324 KB Output is correct
7 Correct 177 ms 47276 KB Output is correct
8 Correct 165 ms 46804 KB Output is correct
9 Correct 180 ms 47064 KB Output is correct
10 Correct 167 ms 46600 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 5 ms 17496 KB Output is correct
8 Correct 4 ms 17244 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 5 ms 16984 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct
16 Correct 4 ms 17244 KB Output is correct
17 Correct 3 ms 17244 KB Output is correct
18 Correct 4 ms 16988 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 4 ms 17244 KB Output is correct
21 Correct 4 ms 16988 KB Output is correct
22 Correct 3 ms 14940 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 5 ms 17240 KB Output is correct
25 Correct 4 ms 16988 KB Output is correct
26 Correct 4 ms 17240 KB Output is correct
27 Correct 3 ms 17240 KB Output is correct
28 Correct 4 ms 17244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 5 ms 17496 KB Output is correct
9 Correct 4 ms 17244 KB Output is correct
10 Correct 121 ms 48216 KB Output is correct
11 Correct 148 ms 55636 KB Output is correct
12 Correct 150 ms 54608 KB Output is correct
13 Correct 180 ms 56912 KB Output is correct
14 Correct 151 ms 61180 KB Output is correct
15 Correct 3 ms 16988 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 5 ms 16984 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 4 ms 16988 KB Output is correct
21 Correct 4 ms 17244 KB Output is correct
22 Correct 3 ms 17244 KB Output is correct
23 Correct 4 ms 16988 KB Output is correct
24 Correct 4 ms 16988 KB Output is correct
25 Correct 4 ms 17244 KB Output is correct
26 Correct 4 ms 16988 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 16988 KB Output is correct
29 Correct 5 ms 17240 KB Output is correct
30 Correct 4 ms 16988 KB Output is correct
31 Correct 4 ms 17240 KB Output is correct
32 Correct 3 ms 17240 KB Output is correct
33 Correct 4 ms 17244 KB Output is correct
34 Correct 15 ms 20828 KB Output is correct
35 Correct 156 ms 55100 KB Output is correct
36 Correct 145 ms 48692 KB Output is correct
37 Correct 163 ms 44624 KB Output is correct
38 Correct 140 ms 43600 KB Output is correct
39 Correct 120 ms 42716 KB Output is correct
40 Correct 106 ms 41812 KB Output is correct
41 Correct 156 ms 50772 KB Output is correct
42 Correct 168 ms 55688 KB Output is correct
43 Correct 142 ms 58960 KB Output is correct
44 Correct 127 ms 45760 KB Output is correct
45 Correct 145 ms 47348 KB Output is correct
46 Correct 172 ms 48708 KB Output is correct
47 Correct 167 ms 44628 KB Output is correct
48 Correct 154 ms 45648 KB Output is correct
49 Correct 68 ms 30228 KB Output is correct
50 Correct 56 ms 26964 KB Output is correct
51 Correct 111 ms 44632 KB Output is correct
52 Correct 188 ms 53572 KB Output is correct
53 Correct 185 ms 51976 KB Output is correct
54 Correct 230 ms 60500 KB Output is correct
55 Correct 153 ms 62072 KB Output is correct
56 Correct 185 ms 51280 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 5 ms 17496 KB Output is correct
8 Correct 4 ms 17244 KB Output is correct
9 Correct 121 ms 48216 KB Output is correct
10 Correct 148 ms 55636 KB Output is correct
11 Correct 150 ms 54608 KB Output is correct
12 Correct 180 ms 56912 KB Output is correct
13 Correct 151 ms 61180 KB Output is correct
14 Correct 141 ms 47368 KB Output is correct
15 Correct 366 ms 57180 KB Output is correct
16 Correct 411 ms 52880 KB Output is correct
17 Correct 370 ms 62492 KB Output is correct
18 Correct 398 ms 59472 KB Output is correct
19 Correct 176 ms 46684 KB Output is correct
20 Correct 204 ms 47472 KB Output is correct
21 Correct 202 ms 47228 KB Output is correct
22 Correct 201 ms 47324 KB Output is correct
23 Correct 177 ms 47276 KB Output is correct
24 Correct 165 ms 46804 KB Output is correct
25 Correct 180 ms 47064 KB Output is correct
26 Correct 167 ms 46600 KB Output is correct
27 Correct 3 ms 16988 KB Output is correct
28 Correct 3 ms 16988 KB Output is correct
29 Correct 3 ms 16988 KB Output is correct
30 Correct 5 ms 16984 KB Output is correct
31 Correct 3 ms 16988 KB Output is correct
32 Correct 4 ms 16988 KB Output is correct
33 Correct 4 ms 17244 KB Output is correct
34 Correct 3 ms 17244 KB Output is correct
35 Correct 4 ms 16988 KB Output is correct
36 Correct 15 ms 20828 KB Output is correct
37 Correct 156 ms 55100 KB Output is correct
38 Correct 145 ms 48692 KB Output is correct
39 Correct 163 ms 44624 KB Output is correct
40 Correct 140 ms 43600 KB Output is correct
41 Correct 120 ms 42716 KB Output is correct
42 Correct 106 ms 41812 KB Output is correct
43 Correct 156 ms 50772 KB Output is correct
44 Correct 168 ms 55688 KB Output is correct
45 Correct 142 ms 58960 KB Output is correct
46 Correct 127 ms 45760 KB Output is correct
47 Correct 25 ms 21588 KB Output is correct
48 Correct 439 ms 56856 KB Output is correct
49 Correct 350 ms 53292 KB Output is correct
50 Correct 403 ms 51252 KB Output is correct
51 Correct 329 ms 50256 KB Output is correct
52 Correct 335 ms 48528 KB Output is correct
53 Correct 226 ms 45816 KB Output is correct
54 Correct 385 ms 55772 KB Output is correct
55 Correct 366 ms 58676 KB Output is correct
56 Correct 371 ms 65028 KB Output is correct
57 Correct 326 ms 50996 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 5 ms 17496 KB Output is correct
9 Correct 4 ms 17244 KB Output is correct
10 Correct 121 ms 48216 KB Output is correct
11 Correct 148 ms 55636 KB Output is correct
12 Correct 150 ms 54608 KB Output is correct
13 Correct 180 ms 56912 KB Output is correct
14 Correct 151 ms 61180 KB Output is correct
15 Correct 141 ms 47368 KB Output is correct
16 Correct 366 ms 57180 KB Output is correct
17 Correct 411 ms 52880 KB Output is correct
18 Correct 370 ms 62492 KB Output is correct
19 Correct 398 ms 59472 KB Output is correct
20 Correct 176 ms 46684 KB Output is correct
21 Correct 204 ms 47472 KB Output is correct
22 Correct 202 ms 47228 KB Output is correct
23 Correct 201 ms 47324 KB Output is correct
24 Correct 177 ms 47276 KB Output is correct
25 Correct 165 ms 46804 KB Output is correct
26 Correct 180 ms 47064 KB Output is correct
27 Correct 167 ms 46600 KB Output is correct
28 Correct 3 ms 16988 KB Output is correct
29 Correct 3 ms 16988 KB Output is correct
30 Correct 3 ms 16988 KB Output is correct
31 Correct 5 ms 16984 KB Output is correct
32 Correct 3 ms 16988 KB Output is correct
33 Correct 4 ms 16988 KB Output is correct
34 Correct 4 ms 17244 KB Output is correct
35 Correct 3 ms 17244 KB Output is correct
36 Correct 4 ms 16988 KB Output is correct
37 Correct 15 ms 20828 KB Output is correct
38 Correct 156 ms 55100 KB Output is correct
39 Correct 145 ms 48692 KB Output is correct
40 Correct 163 ms 44624 KB Output is correct
41 Correct 140 ms 43600 KB Output is correct
42 Correct 120 ms 42716 KB Output is correct
43 Correct 106 ms 41812 KB Output is correct
44 Correct 156 ms 50772 KB Output is correct
45 Correct 168 ms 55688 KB Output is correct
46 Correct 142 ms 58960 KB Output is correct
47 Correct 127 ms 45760 KB Output is correct
48 Correct 25 ms 21588 KB Output is correct
49 Correct 439 ms 56856 KB Output is correct
50 Correct 350 ms 53292 KB Output is correct
51 Correct 403 ms 51252 KB Output is correct
52 Correct 329 ms 50256 KB Output is correct
53 Correct 335 ms 48528 KB Output is correct
54 Correct 226 ms 45816 KB Output is correct
55 Correct 385 ms 55772 KB Output is correct
56 Correct 366 ms 58676 KB Output is correct
57 Correct 371 ms 65028 KB Output is correct
58 Correct 326 ms 50996 KB Output is correct
59 Execution timed out 2063 ms 25940 KB Time limit exceeded
60 Halted 0 ms 0 KB -