oj.uz

Submission #437532

# Submission time Handle Problem Language Result Execution time Memory
437532 2021-06-26T12:47:43 Z Sohsoh84 Swapping Cities (APIO20_swap) C++14
100 / 100
 450 ms 81952 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

int n, m, P[MAXN], H[MAXN], deg[MAXN], E[MAXN];
vector<int> C[MAXN];
vector<pll> par[MAXN];
vector<pair<ll, pll>> edges;

inline void Union(int v, int u, int ind) {
	deg[v]++;
	deg[u]++;
	bool B = (deg[v] > 2 || deg[u] > 2);
	
	v = P[v], u = P[u];
	if (v == u) {
		E[v]++;
		if ((B || E[v] >= C[v].size()) && H[v] < 0)
			for (int e : C[v])
				H[e] = ind;
		return;
	}
	
	if (C[v].size() > C[u].size()) swap(v, u);
	
	E[u] += E[v] + 1;
	B |= (E[u] >= C[u].size() + C[v].size());
	B |= (H[v] >= 0 || H[u] >= 0);
	
	if (B) {
		if (H[v] < 0)
			for (int e : C[v])
				H[e] = ind;
		if (H[u] < 0)
			for (int e : C[u])
				H[e] = ind;
	}

	for (int e : C[v]) {
		C[u].push_back(e);
		par[e].push_back({ind, u});
		P[e] = u;
	}

	C[v].clear();
}

inline int Par(int v, int t) {
	auto it = lower_bound(all(par[v]), make_pair(t + 1, -1));
	it--;
	return it -> Y;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N, m = M;
	for (int i = 1; i <= n; i++) {
		P[i] = i; 
		C[i].push_back(i); 
		par[i].push_back({-1, i});
		H[i] = -1;
	}

	for (int i = 0; i < m; i++) {
		int v = V[i] + 1, u = U[i] + 1, w = W[i];
		edges.push_back({w, {v, u}});
	}

	sort(all(edges));
	for (int i = 0; i < m; i++)
		Union(edges[i].Y.X, edges[i].Y.Y, i);
}

int getMinimumFuelCapacity(int u, int v) {
	u++;
	v++;
 	if (H[u] < 0 || H[v] < 0 || P[v] != P[u]) return -1;
	
	int L = 0, R = m - 1;
	while (L < R) {
		int mid = (L + R) >> 1;
		if (H[u] <= mid && H[v] <= mid && Par(v, mid) == Par(u, mid)) R = mid;
		else L = mid + 1;
	}
	
	return edges[L].X;
}

Compilation message

swap.cpp: In function 'void Union(int, int, int)':
swap.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if ((B || E[v] >= C[v].size()) && H[v] < 0)
      |             ~~~~~^~~~~~~~~~~~~~
swap.cpp:42:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  B |= (E[u] >= C[u].size() + C[v].size());
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 28 ms 47180 KB Output is correct
3 Correct 28 ms 47276 KB Output is correct
4 Correct 27 ms 47356 KB Output is correct
5 Correct 28 ms 47468 KB Output is correct
6 Correct 28 ms 47436 KB Output is correct
7 Correct 28 ms 47484 KB Output is correct
8 Correct 29 ms 47444 KB Output is correct
9 Correct 186 ms 66524 KB Output is correct
10 Correct 255 ms 70524 KB Output is correct
11 Correct 223 ms 70120 KB Output is correct
12 Correct 257 ms 71612 KB Output is correct
13 Correct 159 ms 63644 KB Output is correct
14 Correct 197 ms 66748 KB Output is correct
15 Correct 313 ms 75136 KB Output is correct
16 Correct 334 ms 74436 KB Output is correct
17 Correct 348 ms 75892 KB Output is correct
18 Correct 224 ms 67760 KB Output is correct
19 Correct 103 ms 55996 KB Output is correct
20 Correct 328 ms 76344 KB Output is correct
21 Correct 312 ms 75648 KB Output is correct
22 Correct 325 ms 77400 KB Output is correct
23 Correct 240 ms 69288 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 28 ms 47180 KB Output is correct
3 Correct 260 ms 65688 KB Output is correct
4 Correct 290 ms 66164 KB Output is correct
5 Correct 284 ms 66296 KB Output is correct
6 Correct 272 ms 66068 KB Output is correct
7 Correct 282 ms 66228 KB Output is correct
8 Correct 255 ms 65728 KB Output is correct
9 Correct 266 ms 65968 KB Output is correct
10 Correct 260 ms 65648 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 28 ms 47180 KB Output is correct
3 Correct 28 ms 47276 KB Output is correct
4 Correct 27 ms 47356 KB Output is correct
5 Correct 28 ms 47468 KB Output is correct
6 Correct 28 ms 47436 KB Output is correct
7 Correct 28 ms 47484 KB Output is correct
8 Correct 29 ms 47444 KB Output is correct
9 Correct 29 ms 47180 KB Output is correct
10 Correct 30 ms 47440 KB Output is correct
11 Correct 33 ms 47428 KB Output is correct
12 Correct 30 ms 47464 KB Output is correct
13 Correct 32 ms 47436 KB Output is correct
14 Correct 30 ms 47448 KB Output is correct
15 Correct 30 ms 47408 KB Output is correct
16 Correct 28 ms 47428 KB Output is correct
17 Correct 28 ms 47428 KB Output is correct
18 Correct 29 ms 47428 KB Output is correct
19 Correct 29 ms 47472 KB Output is correct
20 Correct 29 ms 47428 KB Output is correct
21 Correct 29 ms 47320 KB Output is correct
22 Correct 28 ms 47448 KB Output is correct
23 Correct 34 ms 47296 KB Output is correct
24 Correct 31 ms 47628 KB Output is correct
25 Correct 29 ms 47400 KB Output is correct
26 Correct 30 ms 47500 KB Output is correct
27 Correct 29 ms 47408 KB Output is correct
28 Correct 35 ms 47428 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 29 ms 47180 KB Output is correct
3 Correct 28 ms 47180 KB Output is correct
4 Correct 28 ms 47276 KB Output is correct
5 Correct 27 ms 47356 KB Output is correct
6 Correct 28 ms 47468 KB Output is correct
7 Correct 28 ms 47436 KB Output is correct
8 Correct 28 ms 47484 KB Output is correct
9 Correct 29 ms 47444 KB Output is correct
10 Correct 186 ms 66524 KB Output is correct
11 Correct 255 ms 70524 KB Output is correct
12 Correct 223 ms 70120 KB Output is correct
13 Correct 257 ms 71612 KB Output is correct
14 Correct 159 ms 63644 KB Output is correct
15 Correct 30 ms 47440 KB Output is correct
16 Correct 33 ms 47428 KB Output is correct
17 Correct 30 ms 47464 KB Output is correct
18 Correct 32 ms 47436 KB Output is correct
19 Correct 30 ms 47448 KB Output is correct
20 Correct 30 ms 47408 KB Output is correct
21 Correct 28 ms 47428 KB Output is correct
22 Correct 28 ms 47428 KB Output is correct
23 Correct 29 ms 47428 KB Output is correct
24 Correct 29 ms 47472 KB Output is correct
25 Correct 29 ms 47428 KB Output is correct
26 Correct 29 ms 47320 KB Output is correct
27 Correct 28 ms 47448 KB Output is correct
28 Correct 34 ms 47296 KB Output is correct
29 Correct 31 ms 47628 KB Output is correct
30 Correct 29 ms 47400 KB Output is correct
31 Correct 30 ms 47500 KB Output is correct
32 Correct 29 ms 47408 KB Output is correct
33 Correct 35 ms 47428 KB Output is correct
34 Correct 44 ms 50072 KB Output is correct
35 Correct 289 ms 71092 KB Output is correct
36 Correct 270 ms 70932 KB Output is correct
37 Correct 294 ms 70452 KB Output is correct
38 Correct 277 ms 69488 KB Output is correct
39 Correct 258 ms 69224 KB Output is correct
40 Correct 215 ms 67132 KB Output is correct
41 Correct 264 ms 71820 KB Output is correct
42 Correct 297 ms 71732 KB Output is correct
43 Correct 162 ms 62916 KB Output is correct
44 Correct 268 ms 69184 KB Output is correct
45 Correct 184 ms 65332 KB Output is correct
46 Correct 279 ms 70896 KB Output is correct
47 Correct 230 ms 67500 KB Output is correct
48 Correct 188 ms 64908 KB Output is correct
49 Correct 102 ms 58024 KB Output is correct
50 Correct 91 ms 55104 KB Output is correct
51 Correct 142 ms 62320 KB Output is correct
52 Correct 324 ms 74068 KB Output is correct
53 Correct 260 ms 70556 KB Output is correct
54 Correct 325 ms 77528 KB Output is correct
55 Correct 166 ms 63208 KB Output is correct
56 Correct 228 ms 69208 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 28 ms 47180 KB Output is correct
3 Correct 28 ms 47276 KB Output is correct
4 Correct 27 ms 47356 KB Output is correct
5 Correct 28 ms 47468 KB Output is correct
6 Correct 28 ms 47436 KB Output is correct
7 Correct 28 ms 47484 KB Output is correct
8 Correct 29 ms 47444 KB Output is correct
9 Correct 186 ms 66524 KB Output is correct
10 Correct 255 ms 70524 KB Output is correct
11 Correct 223 ms 70120 KB Output is correct
12 Correct 257 ms 71612 KB Output is correct
13 Correct 159 ms 63644 KB Output is correct
14 Correct 197 ms 66748 KB Output is correct
15 Correct 313 ms 75136 KB Output is correct
16 Correct 334 ms 74436 KB Output is correct
17 Correct 348 ms 75892 KB Output is correct
18 Correct 224 ms 67760 KB Output is correct
19 Correct 260 ms 65688 KB Output is correct
20 Correct 290 ms 66164 KB Output is correct
21 Correct 284 ms 66296 KB Output is correct
22 Correct 272 ms 66068 KB Output is correct
23 Correct 282 ms 66228 KB Output is correct
24 Correct 255 ms 65728 KB Output is correct
25 Correct 266 ms 65968 KB Output is correct
26 Correct 260 ms 65648 KB Output is correct
27 Correct 30 ms 47440 KB Output is correct
28 Correct 33 ms 47428 KB Output is correct
29 Correct 30 ms 47464 KB Output is correct
30 Correct 32 ms 47436 KB Output is correct
31 Correct 30 ms 47448 KB Output is correct
32 Correct 30 ms 47408 KB Output is correct
33 Correct 28 ms 47428 KB Output is correct
34 Correct 28 ms 47428 KB Output is correct
35 Correct 29 ms 47428 KB Output is correct
36 Correct 44 ms 50072 KB Output is correct
37 Correct 289 ms 71092 KB Output is correct
38 Correct 270 ms 70932 KB Output is correct
39 Correct 294 ms 70452 KB Output is correct
40 Correct 277 ms 69488 KB Output is correct
41 Correct 258 ms 69224 KB Output is correct
42 Correct 215 ms 67132 KB Output is correct
43 Correct 264 ms 71820 KB Output is correct
44 Correct 297 ms 71732 KB Output is correct
45 Correct 162 ms 62916 KB Output is correct
46 Correct 268 ms 69184 KB Output is correct
47 Correct 55 ms 50492 KB Output is correct
48 Correct 386 ms 76208 KB Output is correct
49 Correct 375 ms 75592 KB Output is correct
50 Correct 425 ms 75548 KB Output is correct
51 Correct 433 ms 74920 KB Output is correct
52 Correct 408 ms 73116 KB Output is correct
53 Correct 324 ms 67624 KB Output is correct
54 Correct 370 ms 76836 KB Output is correct
55 Correct 366 ms 76900 KB Output is correct
56 Correct 301 ms 68504 KB Output is correct
57 Correct 424 ms 74404 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47180 KB Output is correct
2 Correct 29 ms 47180 KB Output is correct
3 Correct 28 ms 47180 KB Output is correct
4 Correct 28 ms 47276 KB Output is correct
5 Correct 27 ms 47356 KB Output is correct
6 Correct 28 ms 47468 KB Output is correct
7 Correct 28 ms 47436 KB Output is correct
8 Correct 28 ms 47484 KB Output is correct
9 Correct 29 ms 47444 KB Output is correct
10 Correct 186 ms 66524 KB Output is correct
11 Correct 255 ms 70524 KB Output is correct
12 Correct 223 ms 70120 KB Output is correct
13 Correct 257 ms 71612 KB Output is correct
14 Correct 159 ms 63644 KB Output is correct
15 Correct 197 ms 66748 KB Output is correct
16 Correct 313 ms 75136 KB Output is correct
17 Correct 334 ms 74436 KB Output is correct
18 Correct 348 ms 75892 KB Output is correct
19 Correct 224 ms 67760 KB Output is correct
20 Correct 260 ms 65688 KB Output is correct
21 Correct 290 ms 66164 KB Output is correct
22 Correct 284 ms 66296 KB Output is correct
23 Correct 272 ms 66068 KB Output is correct
24 Correct 282 ms 66228 KB Output is correct
25 Correct 255 ms 65728 KB Output is correct
26 Correct 266 ms 65968 KB Output is correct
27 Correct 260 ms 65648 KB Output is correct
28 Correct 30 ms 47440 KB Output is correct
29 Correct 33 ms 47428 KB Output is correct
30 Correct 30 ms 47464 KB Output is correct
31 Correct 32 ms 47436 KB Output is correct
32 Correct 30 ms 47448 KB Output is correct
33 Correct 30 ms 47408 KB Output is correct
34 Correct 28 ms 47428 KB Output is correct
35 Correct 28 ms 47428 KB Output is correct
36 Correct 29 ms 47428 KB Output is correct
37 Correct 44 ms 50072 KB Output is correct
38 Correct 289 ms 71092 KB Output is correct
39 Correct 270 ms 70932 KB Output is correct
40 Correct 294 ms 70452 KB Output is correct
41 Correct 277 ms 69488 KB Output is correct
42 Correct 258 ms 69224 KB Output is correct
43 Correct 215 ms 67132 KB Output is correct
44 Correct 264 ms 71820 KB Output is correct
45 Correct 297 ms 71732 KB Output is correct
46 Correct 162 ms 62916 KB Output is correct
47 Correct 268 ms 69184 KB Output is correct
48 Correct 55 ms 50492 KB Output is correct
49 Correct 386 ms 76208 KB Output is correct
50 Correct 375 ms 75592 KB Output is correct
51 Correct 425 ms 75548 KB Output is correct
52 Correct 433 ms 74920 KB Output is correct
53 Correct 408 ms 73116 KB Output is correct
54 Correct 324 ms 67624 KB Output is correct
55 Correct 370 ms 76836 KB Output is correct
56 Correct 366 ms 76900 KB Output is correct
57 Correct 301 ms 68504 KB Output is correct
58 Correct 424 ms 74404 KB Output is correct
59 Correct 103 ms 55996 KB Output is correct
60 Correct 328 ms 76344 KB Output is correct
61 Correct 312 ms 75648 KB Output is correct
62 Correct 325 ms 77400 KB Output is correct
63 Correct 240 ms 69288 KB Output is correct
64 Correct 29 ms 47472 KB Output is correct
65 Correct 29 ms 47428 KB Output is correct
66 Correct 29 ms 47320 KB Output is correct
67 Correct 28 ms 47448 KB Output is correct
68 Correct 34 ms 47296 KB Output is correct
69 Correct 31 ms 47628 KB Output is correct
70 Correct 29 ms 47400 KB Output is correct
71 Correct 30 ms 47500 KB Output is correct
72 Correct 29 ms 47408 KB Output is correct
73 Correct 35 ms 47428 KB Output is correct
74 Correct 184 ms 65332 KB Output is correct
75 Correct 279 ms 70896 KB Output is correct
76 Correct 230 ms 67500 KB Output is correct
77 Correct 188 ms 64908 KB Output is correct
78 Correct 102 ms 58024 KB Output is correct
79 Correct 91 ms 55104 KB Output is correct
80 Correct 142 ms 62320 KB Output is correct
81 Correct 324 ms 74068 KB Output is correct
82 Correct 260 ms 70556 KB Output is correct
83 Correct 325 ms 77528 KB Output is correct
84 Correct 166 ms 63208 KB Output is correct
85 Correct 228 ms 69208 KB Output is correct
86 Correct 101 ms 54828 KB Output is correct
87 Correct 385 ms 75156 KB Output is correct
88 Correct 416 ms 75516 KB Output is correct
89 Correct 307 ms 68740 KB Output is correct
90 Correct 204 ms 61844 KB Output is correct
91 Correct 212 ms 62132 KB Output is correct
92 Correct 305 ms 67188 KB Output is correct
93 Correct 450 ms 78052 KB Output is correct
94 Correct 439 ms 75404 KB Output is correct
95 Correct 449 ms 81952 KB Output is correct
96 Correct 329 ms 68380 KB Output is correct
97 Correct 409 ms 72336 KB Output is correct