oj.uz

Submission #409863

# Submission time Handle Problem Language Result Execution time Memory
409863 2021-05-21T17:20:25 Z jhwest2 Swapping Cities (APIO20_swap) C++14
13 / 100
 453 ms 45072 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 1e5 + 10;
const int INF = 1e9 + 10;

int n, m, Deg[M], Cnt[M], Mx[M], Sz[M], Par[M], A[M], Dep[M], P[20][M], B[20][M];
vector<int> V[M];
vector<pint> G[M];
pair<int, pint> E[M << 1];

int Find(int u) {
	return u == Par[u] ? u : Par[u] = Find(Par[u]);
}
bool is_line(int u) {
	int x = Find(u);
	return Mx[x] <= 2 && Cnt[x] == Sz[x] - 1;
}
void Union(int u, int v, int d) {
	if (Find(u) == Find(v)) {
		int x = Find(u);
		Mx[x] = max({ Mx[x], ++Deg[u], ++Deg[v] });
		Cnt[x]++;
		if (!is_line(x)) {
			for (int k : V[x]) A[k] = d; V[x].clear();
		}
		return;
	}
	int x = Find(u), y = Find(v);
	G[x].emplace_back(d, y); G[y].emplace_back(d, x);
	if (V[x].size() < V[y].size()) {
		swap(x, y), swap(u, v);
	}
	Mx[x] = max({ Mx[x], Mx[y], ++Deg[u], ++Deg[v] });
	Cnt[x] += Cnt[y] + 1; Sz[x] += Sz[y];
	for (int k : V[y]) V[x].push_back(k); V[y].clear();
	Par[y] = x;
	if (!is_line(x)) {
		for (int k : V[x]) A[k] = d; V[x].clear();
	}
}
void dfs(int p, int cur) {
	for (auto [d, x] : G[cur]) if (p != x) {
		P[0][x] = cur; Dep[x] = Dep[cur] + 1; B[0][x] = d;
		for (int i = 1; i < 20; i++) {
			P[i][x] = P[i - 1][P[i - 1][x]];
			B[i][x] = max(B[i - 1][x], B[i - 1][P[i - 1][x]]);
		}
		dfs(cur, x);
	}
}
int query(int u, int v) {
	if (Dep[u] < Dep[v]) swap(u, v);
	int ret = INF;
	for (int i = 19; i >= 0; i--) {
		if (Dep[u] - Dep[v] >> i & 1) {
			ret = min(ret, B[i][u]); u = P[i][u];
		}
	}
	for (int i = 19; i >= 0; i--) {
		if (P[i][u] != P[i][v]) {
			ret = min({ ret, B[i][u], B[i][v] });
			u = P[i][u]; v = P[i][v];
		}
	}
	return u == v ? ret : min({ ret, B[0][u], B[0][v] });
}
void init(int N, int M, vector<int> _U, vector<int> _V, vector<int> _W) {
	n = N; m = M;
	for (int i = 0; i < m; i++) {
		E[i] = { _W[i], {_U[i], _V[i]} };
	}
	sort(E, E + m);
	for (int i = 0; i < n; i++) {
		V[i].push_back(i); Par[i] = i; Sz[i] = 1; A[i] = INF;
	}
	for (int i = 0; i < m; i++) {
		auto [u, v] = E[i].vb;
		Union(u, v, E[i].va);
	}
	dfs(0, 0);

}

int getMinimumFuelCapacity(int u, int v) {
	int ret = max({ query(u, v), A[u], A[v] });
	return ret == INF ? -1 : ret;
}

Compilation message

swap.cpp: In function 'void Union(int, int, int)':
swap.cpp:29:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   29 |    for (int k : V[x]) A[k] = d; V[x].clear();
      |    ^~~
swap.cpp:29:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   29 |    for (int k : V[x]) A[k] = d; V[x].clear();
      |                                 ^
swap.cpp:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |  for (int k : V[y]) V[x].push_back(k); V[y].clear();
      |  ^~~
swap.cpp:40:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |  for (int k : V[y]) V[x].push_back(k); V[y].clear();
      |                                        ^
swap.cpp:43:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |   for (int k : V[x]) A[k] = d; V[x].clear();
      |   ^~~
swap.cpp:43:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |   for (int k : V[x]) A[k] = d; V[x].clear();
      |                                ^
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |  for (auto [d, x] : G[cur]) if (p != x) {
      |            ^
swap.cpp: In function 'int query(int, int)':
swap.cpp:60:14: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   60 |   if (Dep[u] - Dep[v] >> i & 1) {
      |       ~~~~~~~^~~~~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:82:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |   auto [u, v] = E[i].vb;
      |        ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 148 ms 30372 KB Output is correct
10 Correct 180 ms 36028 KB Output is correct
11 Correct 182 ms 35548 KB Output is correct
12 Correct 203 ms 37052 KB Output is correct
13 Correct 154 ms 33800 KB Output is correct
14 Correct 156 ms 30640 KB Output is correct
15 Correct 337 ms 38300 KB Output is correct
16 Correct 324 ms 37312 KB Output is correct
17 Correct 340 ms 39060 KB Output is correct
18 Correct 284 ms 35608 KB Output is correct
19 Correct 97 ms 13604 KB Output is correct
20 Correct 356 ms 39720 KB Output is correct
21 Correct 326 ms 38836 KB Output is correct
22 Correct 345 ms 40736 KB Output is correct
23 Correct 293 ms 37400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 430 ms 42340 KB Output is correct
4 Correct 430 ms 45072 KB Output is correct
5 Correct 431 ms 44328 KB Output is correct
6 Correct 413 ms 45016 KB Output is correct
7 Correct 453 ms 44792 KB Output is correct
8 Correct 395 ms 43248 KB Output is correct
9 Correct 430 ms 44512 KB Output is correct
10 Correct 407 ms 42876 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Incorrect 4 ms 5452 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 148 ms 30372 KB Output is correct
11 Correct 180 ms 36028 KB Output is correct
12 Correct 182 ms 35548 KB Output is correct
13 Correct 203 ms 37052 KB Output is correct
14 Correct 154 ms 33800 KB Output is correct
15 Incorrect 4 ms 5452 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 148 ms 30372 KB Output is correct
10 Correct 180 ms 36028 KB Output is correct
11 Correct 182 ms 35548 KB Output is correct
12 Correct 203 ms 37052 KB Output is correct
13 Correct 154 ms 33800 KB Output is correct
14 Correct 156 ms 30640 KB Output is correct
15 Correct 337 ms 38300 KB Output is correct
16 Correct 324 ms 37312 KB Output is correct
17 Correct 340 ms 39060 KB Output is correct
18 Correct 284 ms 35608 KB Output is correct
19 Correct 430 ms 42340 KB Output is correct
20 Correct 430 ms 45072 KB Output is correct
21 Correct 431 ms 44328 KB Output is correct
22 Correct 413 ms 45016 KB Output is correct
23 Correct 453 ms 44792 KB Output is correct
24 Correct 395 ms 43248 KB Output is correct
25 Correct 430 ms 44512 KB Output is correct
26 Correct 407 ms 42876 KB Output is correct
27 Incorrect 4 ms 5452 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 148 ms 30372 KB Output is correct
11 Correct 180 ms 36028 KB Output is correct
12 Correct 182 ms 35548 KB Output is correct
13 Correct 203 ms 37052 KB Output is correct
14 Correct 154 ms 33800 KB Output is correct
15 Correct 156 ms 30640 KB Output is correct
16 Correct 337 ms 38300 KB Output is correct
17 Correct 324 ms 37312 KB Output is correct
18 Correct 340 ms 39060 KB Output is correct
19 Correct 284 ms 35608 KB Output is correct
20 Correct 430 ms 42340 KB Output is correct
21 Correct 430 ms 45072 KB Output is correct
22 Correct 431 ms 44328 KB Output is correct
23 Correct 413 ms 45016 KB Output is correct
24 Correct 453 ms 44792 KB Output is correct
25 Correct 395 ms 43248 KB Output is correct
26 Correct 430 ms 44512 KB Output is correct
27 Correct 407 ms 42876 KB Output is correct
28 Incorrect 4 ms 5452 KB Output isn't correct
29 Halted 0 ms 0 KB -