oj.uz

Submission #409864

# Submission time Handle Problem Language Result Execution time Memory
409864 2021-05-21T17:26:15 Z jhwest2 Swapping Cities (APIO20_swap) C++14
0 / 100
 418 ms 40924 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 = max(ret, B[i][u]); u = P[i][u];
		}
	}
	for (int i = 19; i >= 0; i--) {
		if (P[i][u] != P[i][v]) {
			ret = max({ ret, B[i][u], B[i][v] });
			u = P[i][u]; v = P[i][v];
		}
	}
	return u == v ? ret : max({ 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
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 5 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 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 140 ms 30368 KB Output is correct
10 Correct 183 ms 36048 KB Output is correct
11 Correct 182 ms 35612 KB Output is correct
12 Correct 203 ms 37156 KB Output is correct
13 Correct 156 ms 33816 KB Output is correct
14 Correct 175 ms 30612 KB Output is correct
15 Correct 337 ms 38280 KB Output is correct
16 Correct 337 ms 37396 KB Output is correct
17 Correct 349 ms 39036 KB Output is correct
18 Correct 284 ms 35480 KB Output is correct
19 Incorrect 122 ms 12468 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 418 ms 40924 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 5 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 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 Incorrect 3 ms 5196 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5196 KB Output isn't correct

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 5 ms 5324 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 5 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 140 ms 30368 KB Output is correct
10 Correct 183 ms 36048 KB Output is correct
11 Correct 182 ms 35612 KB Output is correct
12 Correct 203 ms 37156 KB Output is correct
13 Correct 156 ms 33816 KB Output is correct
14 Correct 175 ms 30612 KB Output is correct
15 Correct 337 ms 38280 KB Output is correct
16 Correct 337 ms 37396 KB Output is correct
17 Correct 349 ms 39036 KB Output is correct
18 Correct 284 ms 35480 KB Output is correct
19 Incorrect 418 ms 40924 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5196 KB Output isn't correct