oj.uz

Submission #892086

# Submission time Handle Problem Language Result Execution time Memory
892086 2023-12-24T18:51:15 Z omeganot Swapping Cities (APIO20_swap) C++11
7 / 100
 2000 ms 65048 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({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]);
			}
		}
	} 
}

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 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 4 ms 16984 KB Output is correct
7 Correct 4 ms 17244 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 128 ms 49492 KB Output is correct
10 Correct 156 ms 56884 KB Output is correct
11 Correct 152 ms 55976 KB Output is correct
12 Correct 157 ms 58132 KB Output is correct
13 Correct 143 ms 62312 KB Output is correct
14 Correct 128 ms 48512 KB Output is correct
15 Correct 377 ms 59484 KB Output is correct
16 Correct 346 ms 55120 KB Output is correct
17 Correct 394 ms 65048 KB Output is correct
18 Correct 371 ms 61780 KB Output is correct
19 Execution timed out 2063 ms 27136 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 3 ms 14940 KB Output is correct
3 Correct 172 ms 48904 KB Output is correct
4 Correct 176 ms 49568 KB Output is correct
5 Correct 173 ms 49524 KB Output is correct
6 Correct 177 ms 49420 KB Output is correct
7 Correct 171 ms 49612 KB Output is correct
8 Correct 168 ms 48652 KB Output is correct
9 Correct 203 ms 49452 KB Output is correct
10 Correct 173 ms 48736 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 17244 KB Output is correct
7 Correct 4 ms 16984 KB Output is correct
8 Correct 4 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 128 ms 49492 KB Output is correct
11 Correct 156 ms 56884 KB Output is correct
12 Correct 152 ms 55976 KB Output is correct
13 Correct 157 ms 58132 KB Output is correct
14 Correct 143 ms 62312 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct
16 Correct 3 ms 17244 KB Output is correct
17 Correct 4 ms 17084 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 5 ms 16988 KB Output is correct
21 Correct 4 ms 17244 KB Output is correct
22 Correct 4 ms 17244 KB Output is correct
23 Correct 6 ms 16988 KB Output is correct
24 Correct 3 ms 16988 KB Output is correct
25 Correct 3 ms 17244 KB Output is correct
26 Correct 3 ms 16988 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 3 ms 16988 KB Output is correct
29 Correct 6 ms 17244 KB Output is correct
30 Correct 4 ms 17244 KB Output is correct
31 Incorrect 4 ms 17244 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 4 ms 16984 KB Output is correct
7 Correct 4 ms 17244 KB Output is correct
8 Correct 3 ms 17244 KB Output is correct
9 Correct 128 ms 49492 KB Output is correct
10 Correct 156 ms 56884 KB Output is correct
11 Correct 152 ms 55976 KB Output is correct
12 Correct 157 ms 58132 KB Output is correct
13 Correct 143 ms 62312 KB Output is correct
14 Correct 128 ms 48512 KB Output is correct
15 Correct 377 ms 59484 KB Output is correct
16 Correct 346 ms 55120 KB Output is correct
17 Correct 394 ms 65048 KB Output is correct
18 Correct 371 ms 61780 KB Output is correct
19 Correct 172 ms 48904 KB Output is correct
20 Correct 176 ms 49568 KB Output is correct
21 Correct 173 ms 49524 KB Output is correct
22 Correct 177 ms 49420 KB Output is correct
23 Correct 171 ms 49612 KB Output is correct
24 Correct 168 ms 48652 KB Output is correct
25 Correct 203 ms 49452 KB Output is correct
26 Correct 173 ms 48736 KB Output is correct
27 Correct 4 ms 16988 KB Output is correct
28 Correct 3 ms 17244 KB Output is correct
29 Correct 4 ms 17084 KB Output is correct
30 Correct 3 ms 16988 KB Output is correct
31 Correct 3 ms 16988 KB Output is correct
32 Correct 5 ms 16988 KB Output is correct
33 Correct 4 ms 17244 KB Output is correct
34 Correct 4 ms 17244 KB Output is correct
35 Correct 6 ms 16988 KB Output is correct
36 Correct 14 ms 21084 KB Output is correct
37 Correct 155 ms 56976 KB Output is correct
38 Correct 144 ms 50408 KB Output is correct
39 Correct 135 ms 46392 KB Output is correct
40 Correct 125 ms 45208 KB Output is correct
41 Correct 119 ms 44368 KB Output is correct
42 Correct 101 ms 43344 KB Output is correct
43 Incorrect 150 ms 52704 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 17244 KB Output is correct
7 Correct 4 ms 16984 KB Output is correct
8 Correct 4 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 128 ms 49492 KB Output is correct
11 Correct 156 ms 56884 KB Output is correct
12 Correct 152 ms 55976 KB Output is correct
13 Correct 157 ms 58132 KB Output is correct
14 Correct 143 ms 62312 KB Output is correct
15 Correct 128 ms 48512 KB Output is correct
16 Correct 377 ms 59484 KB Output is correct
17 Correct 346 ms 55120 KB Output is correct
18 Correct 394 ms 65048 KB Output is correct
19 Correct 371 ms 61780 KB Output is correct
20 Correct 172 ms 48904 KB Output is correct
21 Correct 176 ms 49568 KB Output is correct
22 Correct 173 ms 49524 KB Output is correct
23 Correct 177 ms 49420 KB Output is correct
24 Correct 171 ms 49612 KB Output is correct
25 Correct 168 ms 48652 KB Output is correct
26 Correct 203 ms 49452 KB Output is correct
27 Correct 173 ms 48736 KB Output is correct
28 Correct 4 ms 16988 KB Output is correct
29 Correct 3 ms 17244 KB Output is correct
30 Correct 4 ms 17084 KB Output is correct
31 Correct 3 ms 16988 KB Output is correct
32 Correct 3 ms 16988 KB Output is correct
33 Correct 5 ms 16988 KB Output is correct
34 Correct 4 ms 17244 KB Output is correct
35 Correct 4 ms 17244 KB Output is correct
36 Correct 6 ms 16988 KB Output is correct
37 Correct 14 ms 21084 KB Output is correct
38 Correct 155 ms 56976 KB Output is correct
39 Correct 144 ms 50408 KB Output is correct
40 Correct 135 ms 46392 KB Output is correct
41 Correct 125 ms 45208 KB Output is correct
42 Correct 119 ms 44368 KB Output is correct
43 Correct 101 ms 43344 KB Output is correct
44 Incorrect 150 ms 52704 KB Output isn't correct
45 Halted 0 ms 0 KB -