oj.uz

Submission #657038

# Submission time Handle Problem Language Result Execution time Memory
657038 2022-11-08T19:17:00 Z 600Mihnea Swapping Cities (APIO20_swap) C++17
100 / 100
 193 ms 17456 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;


const int INF = (int) 1e9 + 7;
int n;
int m;
vector<int> t;
vector<int> dim;
vector<int> is_line;
vector<int> is_endpoint;
vector<int> when;
vector<int> when_join;

int root(int a) {
	if (t[a] == a) {
		return t[a];
	} else {
		return root(t[a]);
	}
}

void join(int a, int b, int val) {
	int x = a, y = b;
	a = root(a);
	b = root(b);
	if (a == b) {
		if (is_line[a] == 1) {
			when[a] = val;
		}
		is_line[a] = 0;
		return;
	}
	if (dim[a] < dim[b]) {
		swap(a, b);
		swap(x, y);
	}
	if (is_line[a] && is_line[b] && is_endpoint[x] && is_endpoint[y]) {
		is_line[a] = 1;
		if (dim[a] > 1) {
			is_endpoint[x] = 0;
		}
		if (dim[b] > 1) {
			is_endpoint[y] = 0;
		}
	} else {
		if (is_line[a] == 1) {
			when[a] = val;
			is_line[a] = 0;
		}
	}
	when_join[b] = val; 
	dim[a] += dim[b];
	t[b] = a;
}

void clr() {
	t.resize(n);
	is_line.resize(n);
	is_endpoint.resize(n);
	dim.resize(n);
	when.resize(n);
	when_join.resize(n);
	for (int i = 0; i < n; i++) {
		t[i] = i;
		is_line[i] = 1;
		is_endpoint[i] = 1;
		dim[i] = 1;
		when[i] = -1;
	}
}

struct Edge {
	int a;
	int b;
	int w;
};

bool operator < (Edge first, Edge second) {
	return first.w < second.w;
}

vector<Edge> edges;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	assert((int) U.size() == m);
	assert((int) V.size() == m);
	assert((int) W.size() == m);
	
	edges.clear();
	for (int i = 0; i < m; i++) {
		edges.push_back({U[i], V[i], W[i]});
	}
	sort(edges.begin(), edges.end());
	clr();
	for (auto &edge : edges) {
		int a = edge.a;
		int b = edge.b;
		int w = edge.w;
		join(a, b, w);
	}
}



int getMinimumFuelCapacity(int x, int y) {
	if (x == y) {
		return 0;
	}
	vector<int> path_x, path_y;
	while (1) {
		path_x.push_back(x);
		if (x == t[x]) {
			break;
		}
		x = t[x];
	}
	while (1) {
		path_y.push_back(y);
		if (y == t[y]) {
			break;
		}
		y = t[y];
	}
	reverse(path_x.begin(), path_x.end());
	reverse(path_y.begin(), path_y.end());
	bool deja = 0;
	int wjoin = 0;
	for (int i = max((int) path_x.size() - 1, (int) path_y.size() -1); i >= 0; i--) {
		if (i < (int) path_x.size() && i < (int) path_y.size() && path_x[i] == path_y[i]) {
			if (deja) {
				return wjoin;
			}
			if (when[path_x[i]] != -1) {
				return max(wjoin, when[path_x[i]]);
			}
		}
		if (i < (int) path_x.size()) {
			if (when[path_x[i]] != -1) deja = 1;
			wjoin = max(wjoin, when_join[path_x[i]]);
		}
		if (i < (int) path_y.size()) {
			if (when[path_y[i]] != -1) deja = 1;
			wjoin = max(wjoin, when_join[path_y[i]]);
		}
	}
	
	return -1;
	exit(0);

	return -1;
	clr();
	for (auto &edge : edges) {
		int a = edge.a;
		int b = edge.b;
		int w = edge.w;
		join(a, b, w);
		//cout << a << " " << b << " | " << w << " and I care about " << x << " " << y << "\n";
		if (root(x) == root(y) && !is_line[root(x)]) {
			return w; 
		}
	}
	return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 31 ms 4796 KB Output is correct
10 Correct 37 ms 5824 KB Output is correct
11 Correct 38 ms 5824 KB Output is correct
12 Correct 42 ms 6172 KB Output is correct
13 Correct 37 ms 6076 KB Output is correct
14 Correct 40 ms 4924 KB Output is correct
15 Correct 146 ms 7712 KB Output is correct
16 Correct 175 ms 7564 KB Output is correct
17 Correct 152 ms 7824 KB Output is correct
18 Correct 116 ms 7960 KB Output is correct
19 Correct 85 ms 4640 KB Output is correct
20 Correct 139 ms 8964 KB Output is correct
21 Correct 147 ms 9012 KB Output is correct
22 Correct 151 ms 9360 KB Output is correct
23 Correct 118 ms 9248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 105 ms 8808 KB Output is correct
4 Correct 110 ms 8976 KB Output is correct
5 Correct 107 ms 9056 KB Output is correct
6 Correct 99 ms 8896 KB Output is correct
7 Correct 106 ms 9108 KB Output is correct
8 Correct 105 ms 8944 KB Output is correct
9 Correct 104 ms 8992 KB Output is correct
10 Correct 127 ms 8788 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 31 ms 4796 KB Output is correct
11 Correct 37 ms 5824 KB Output is correct
12 Correct 38 ms 5824 KB Output is correct
13 Correct 42 ms 6172 KB Output is correct
14 Correct 37 ms 6076 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 6 ms 1044 KB Output is correct
35 Correct 37 ms 6132 KB Output is correct
36 Correct 45 ms 6068 KB Output is correct
37 Correct 42 ms 6092 KB Output is correct
38 Correct 37 ms 6060 KB Output is correct
39 Correct 35 ms 5952 KB Output is correct
40 Correct 34 ms 5508 KB Output is correct
41 Correct 40 ms 6080 KB Output is correct
42 Correct 38 ms 6072 KB Output is correct
43 Correct 37 ms 6080 KB Output is correct
44 Correct 40 ms 6180 KB Output is correct
45 Correct 57 ms 7276 KB Output is correct
46 Correct 38 ms 6080 KB Output is correct
47 Correct 42 ms 6072 KB Output is correct
48 Correct 46 ms 6516 KB Output is correct
49 Correct 57 ms 7140 KB Output is correct
50 Correct 44 ms 4676 KB Output is correct
51 Correct 52 ms 6364 KB Output is correct
52 Correct 64 ms 8332 KB Output is correct
53 Correct 92 ms 8908 KB Output is correct
54 Correct 89 ms 9788 KB Output is correct
55 Correct 36 ms 6080 KB Output is correct
56 Correct 68 ms 8696 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 31 ms 4796 KB Output is correct
10 Correct 37 ms 5824 KB Output is correct
11 Correct 38 ms 5824 KB Output is correct
12 Correct 42 ms 6172 KB Output is correct
13 Correct 37 ms 6076 KB Output is correct
14 Correct 40 ms 4924 KB Output is correct
15 Correct 146 ms 7712 KB Output is correct
16 Correct 175 ms 7564 KB Output is correct
17 Correct 152 ms 7824 KB Output is correct
18 Correct 116 ms 7960 KB Output is correct
19 Correct 105 ms 8808 KB Output is correct
20 Correct 110 ms 8976 KB Output is correct
21 Correct 107 ms 9056 KB Output is correct
22 Correct 99 ms 8896 KB Output is correct
23 Correct 106 ms 9108 KB Output is correct
24 Correct 105 ms 8944 KB Output is correct
25 Correct 104 ms 8992 KB Output is correct
26 Correct 127 ms 8788 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 6 ms 1044 KB Output is correct
37 Correct 37 ms 6132 KB Output is correct
38 Correct 45 ms 6068 KB Output is correct
39 Correct 42 ms 6092 KB Output is correct
40 Correct 37 ms 6060 KB Output is correct
41 Correct 35 ms 5952 KB Output is correct
42 Correct 34 ms 5508 KB Output is correct
43 Correct 40 ms 6080 KB Output is correct
44 Correct 38 ms 6072 KB Output is correct
45 Correct 37 ms 6080 KB Output is correct
46 Correct 40 ms 6180 KB Output is correct
47 Correct 15 ms 1804 KB Output is correct
48 Correct 161 ms 12800 KB Output is correct
49 Correct 151 ms 12932 KB Output is correct
50 Correct 164 ms 12836 KB Output is correct
51 Correct 160 ms 12760 KB Output is correct
52 Correct 144 ms 12452 KB Output is correct
53 Correct 157 ms 11348 KB Output is correct
54 Correct 157 ms 13716 KB Output is correct
55 Correct 155 ms 12764 KB Output is correct
56 Correct 131 ms 12812 KB Output is correct
57 Correct 142 ms 13736 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 31 ms 4796 KB Output is correct
11 Correct 37 ms 5824 KB Output is correct
12 Correct 38 ms 5824 KB Output is correct
13 Correct 42 ms 6172 KB Output is correct
14 Correct 37 ms 6076 KB Output is correct
15 Correct 40 ms 4924 KB Output is correct
16 Correct 146 ms 7712 KB Output is correct
17 Correct 175 ms 7564 KB Output is correct
18 Correct 152 ms 7824 KB Output is correct
19 Correct 116 ms 7960 KB Output is correct
20 Correct 105 ms 8808 KB Output is correct
21 Correct 110 ms 8976 KB Output is correct
22 Correct 107 ms 9056 KB Output is correct
23 Correct 99 ms 8896 KB Output is correct
24 Correct 106 ms 9108 KB Output is correct
25 Correct 105 ms 8944 KB Output is correct
26 Correct 104 ms 8992 KB Output is correct
27 Correct 127 ms 8788 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 6 ms 1044 KB Output is correct
38 Correct 37 ms 6132 KB Output is correct
39 Correct 45 ms 6068 KB Output is correct
40 Correct 42 ms 6092 KB Output is correct
41 Correct 37 ms 6060 KB Output is correct
42 Correct 35 ms 5952 KB Output is correct
43 Correct 34 ms 5508 KB Output is correct
44 Correct 40 ms 6080 KB Output is correct
45 Correct 38 ms 6072 KB Output is correct
46 Correct 37 ms 6080 KB Output is correct
47 Correct 40 ms 6180 KB Output is correct
48 Correct 15 ms 1804 KB Output is correct
49 Correct 161 ms 12800 KB Output is correct
50 Correct 151 ms 12932 KB Output is correct
51 Correct 164 ms 12836 KB Output is correct
52 Correct 160 ms 12760 KB Output is correct
53 Correct 144 ms 12452 KB Output is correct
54 Correct 157 ms 11348 KB Output is correct
55 Correct 157 ms 13716 KB Output is correct
56 Correct 155 ms 12764 KB Output is correct
57 Correct 131 ms 12812 KB Output is correct
58 Correct 142 ms 13736 KB Output is correct
59 Correct 85 ms 4640 KB Output is correct
60 Correct 139 ms 8964 KB Output is correct
61 Correct 147 ms 9012 KB Output is correct
62 Correct 151 ms 9360 KB Output is correct
63 Correct 118 ms 9248 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 340 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 1 ms 340 KB Output is correct
68 Correct 1 ms 340 KB Output is correct
69 Correct 1 ms 340 KB Output is correct
70 Correct 1 ms 340 KB Output is correct
71 Correct 1 ms 340 KB Output is correct
72 Correct 1 ms 340 KB Output is correct
73 Correct 1 ms 340 KB Output is correct
74 Correct 57 ms 7276 KB Output is correct
75 Correct 38 ms 6080 KB Output is correct
76 Correct 42 ms 6072 KB Output is correct
77 Correct 46 ms 6516 KB Output is correct
78 Correct 57 ms 7140 KB Output is correct
79 Correct 44 ms 4676 KB Output is correct
80 Correct 52 ms 6364 KB Output is correct
81 Correct 64 ms 8332 KB Output is correct
82 Correct 92 ms 8908 KB Output is correct
83 Correct 89 ms 9788 KB Output is correct
84 Correct 36 ms 6080 KB Output is correct
85 Correct 68 ms 8696 KB Output is correct
86 Correct 45 ms 4856 KB Output is correct
87 Correct 143 ms 12804 KB Output is correct
88 Correct 153 ms 12840 KB Output is correct
89 Correct 135 ms 12940 KB Output is correct
90 Correct 145 ms 13640 KB Output is correct
91 Correct 141 ms 13420 KB Output is correct
92 Correct 139 ms 13860 KB Output is correct
93 Correct 193 ms 16284 KB Output is correct
94 Correct 168 ms 17164 KB Output is correct
95 Correct 189 ms 17456 KB Output is correct
96 Correct 119 ms 12904 KB Output is correct
97 Correct 143 ms 15268 KB Output is correct