oj.uz

Submission #410187

# Submission time Handle Problem Language Result Execution time Memory
410187 2021-05-22T08:22:55 Z kaage Swapping Cities (APIO20_swap) C++17
37 / 100
 2000 ms 9796 KB 
#line 1 "swap.h"
#include <vector>

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W);

int getMinimumFuelCapacity(int X, int Y);
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#ifndef __clang__
#ifdef ONLINE_JUDGE
#pragma GCC target("avx512f")
#elif defined EVAL
#else
#pragma GCC target("avx2")
#endif
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#line 41 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define REP(i, n) for (int i = 1; i <= int(n); i++)
#define all(V) V.begin(), V.end()

using i128 = __int128_t;
using u128 = __uint128_t;
using uint = unsigned int;
using lint = long long;
using ulint = unsigned long long;
using IP = std::pair<int, int>;
using LP = std::pair<lint, lint>;

constexpr int INF = INT_MAX / 2;
constexpr lint LINF = LLONG_MAX / 2;
constexpr double eps = DBL_EPSILON;
constexpr double PI = 3.141592653589793238462643383279;

template <class T>
class prique : public std::priority_queue<T, std::vector<T>, std::greater<T>> {
};
int popcount(uint x) {
#if __cplusplus >= 202002L
	return std::popcount(x);
#else
#ifndef __clang__
	return __builtin_popcount(x);
#endif
#endif
	x = (x & 0x55555555) + (x >> 1 & 0x55555555);
	x = (x & 0x33333333) + (x >> 2 & 0x33333333);
	x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
	x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
	return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff);
}
template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
	return [f = std::forward<F>(f)](auto&&... args) {
		return f(f, std::forward<decltype(args)>(args)...);
	};
}
template <class T>
constexpr std::vector<T> make_vec(size_t n) {
	return std::vector<T>(n);
}
template <class T, class... Args>
constexpr auto make_vec(size_t n, Args&&... args) {
	return std::vector<decltype(make_vec<T>(args...))>(
		n, make_vec<T>(std::forward<Args>(args)...));
}
template <class T, class U>
std::istream& operator>>(std::istream& ist, std::pair<T, U>& x) {
	return ist >> x.first >> x.second;
}
template <class T, class U>
std::ostream& operator<<(std::ostream& ost, const std::pair<T, U>& x) {
	return ost << x.first << " " << x.second;
}
template <class T, class U>
constexpr inline bool chmax(T& lhs, const U& rhs) noexcept {
	if (lhs < rhs) {
		lhs = rhs;
		return true;
	}
	return false;
}
template <class T, class U>
constexpr inline bool chmin(T& lhs, const U& rhs) noexcept {
	if (lhs > rhs) {
		lhs = rhs;
		return true;
	}
	return false;
}
constexpr inline lint gcd(lint a, lint b) noexcept {
	while (b) {
		lint c = a;
		a = b;
		b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) noexcept { return a / gcd(a, b) * b; }
constexpr bool isprime(lint n) noexcept {
	if (n == 1) return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}
template <class T>
constexpr T mypow(T a, lint b) noexcept {
	T res(1);
	while (true) {
		if (b & 1) res *= a;
		b >>= 1;
		if (!b) break;
		a *= a;
	}
	return res;
}
constexpr lint modpow(lint a, lint b, lint m) noexcept {
	a %= m;
	lint res(1);
	while (b) {
		if (b & 1) {
			res *= a;
			res %= m;
		}
		a *= a;
		a %= m;
		b >>= 1;
	}
	return res;
}
template <class T>
constexpr void printArray(const std::vector<T>& vec, char split = ' ') {
	rep(i, vec.size()) {
		std::cout << vec[i];
		std::cout << (i == (int)vec.size() - 1 ? '\n' : split);
	}
}
template <class InputIter>
constexpr void printArray(InputIter l, InputIter r, char split = ' ') {
	auto rprev = std::prev(r);
	for (auto i = l; i != r; i++) {
		std::cout << *i;
		std::cout << (i == rprev ? '\n' : split);
	}
}
LP extGcd(lint a, lint b) noexcept {
	if (b == 0) return {1, 0};
	LP s = extGcd(b, a % b);
	std::swap(s.first, s.second);
	s.second -= a / b * s.first;
	return s;
}
LP ChineseRem(const lint& b1, const lint& m1, const lint& b2,
			  const lint& m2) noexcept {
	auto p = extGcd(m1, m2);
	lint g = gcd(m1, m2), l = m1 / g * m2;
	lint tmp = (b2 - b1) / g * p.first % (m2 / g);
	lint r = (b1 + m1 * tmp + l) % l;
	return {r, l};
}
int LCS(const std::string& a, const std::string& b) {
	auto dp = make_vec<int>(a.size() + 1, b.size() + 1);
	rep(i, a.size()) {
		rep(j, b.size()) {
			chmax(dp[i + 1][j], dp[i][j]);
			chmax(dp[i][j + 1], dp[i][j]);
			if (a[i] == b[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1);
		}
		chmax(dp[i + 1][b.size()], dp[i][b.size()]);
	}
	rep(j, b.size()) chmax(dp[a.size()][j + 1], dp[a.size()][j]);
	return dp[a.size()][b.size()];
}
template <class T, std::enable_if_t<std::is_convertible<int, T>::value,
									std::nullptr_t> = nullptr>
void compress(std::vector<T>& vec) {
	auto tmp = vec;
	std::sort(all(tmp));
	tmp.erase(std::unique(all(tmp)), tmp.end());
	for (T& i : vec) i = std::lower_bound(all(tmp), i) - tmp.begin();
}
template <class T>
void compress(T* l, T* r) {
	std::vector<T> tmp(l, r);
	std::sort(all(tmp));
	tmp.erase(std::unique(all(tmp)), tmp.end());
	for (auto i = l; i < r; i++) {
		*i = std::lower_bound(all(tmp), *i) - tmp.begin();
	}
}
template <class InputIter>
void compress(InputIter l, InputIter r) {
	std::vector<typename InputIter::value_type> tmp(l, r);
	std::sort(all(tmp));
	tmp.erase(std::unique(all(tmp)), tmp.end());
	for (auto i = l; i < r; i++) {
		*i = std::lower_bound(all(tmp), *i) - tmp.begin();
	}
}
#line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/graph/UnionFind.hpp"
class UnionFind {
  protected:
	std::vector<int> par, size;

  public:
	UnionFind() {}
	UnionFind(int size) { init(size); }
	void init(int size) {
		par.resize(size);
		this->size.resize(size, 1);
		std::iota(all(par), 0);
	}
	int find(int n) {
		if (par[n] == n) return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m) return;
		int a = n, b = m;
		if (size[a] > size[b]) std::swap(a, b);
		par[a] = b;
		size[b] += size[a];
	}
	bool same(int n, int m) { return find(n) == find(m); }
	int getsize(int n) { return size[find(n)]; }
	bool is_root(int n) { return find(n) == n; }
};

/**
 * @title Disjoint set
 */
#line 4 "swap.cpp"
class PersistentUnionFind : UnionFind {
	std::vector<IP> notparent;
	std::vector<int> ok_vec;
	int opcount = 0;

  public:
	PersistentUnionFind(unsigned int size) : UnionFind(size) {
		notparent.resize(size);
		ok_vec.resize(size, INF);
		rep(i, size) {
			par[i] = i;
			notparent[i] = {INF, i};
		}
	}
	int find(int n, int t = INF) {
		if (opcount <= t) {
			if (par[n] == n) return n;
			return par[n] = find(par[n]);
		}
		if (notparent[n].first <= t) return find(notparent[n].second, t);
		return n;
	}
	void unite(int n, int m, bool f = false) {
		n = find(n);
		m = find(m);
		if (n == m) {
			if (f && ok_vec[n] == INF) ok_vec[n] = opcount;
			opcount++;
			return;
		}
		if (size[n] > size[m]) std::swap(n, m);
		par[n] = m;
		notparent[n] = {opcount, m};
		if (ok_vec[m] == INF && (f || ok_vec[n] != INF)) ok_vec[m] = opcount;

		opcount++;
	}
	bool same(int n, int m, int t = INF) { return find(n, t) == find(m, t); }
	bool ok(int x, int t = INF) { return ok_vec[x] <= t; }
};

int N, M;
std::vector<std::pair<int, IP>> edges;
PersistentUnionFind uf(100010);

void init(int n, int m, std::vector<int> U, std::vector<int> V,
		  std::vector<int> W) {
	N = n, M = m;
	edges.reserve(M);
	rep(i, M) edges.push_back({W[i], {U[i], V[i]}});
	std::sort(all(edges));
	std::vector<int> degree(N);
	rep(i, M) {
		degree[edges[i].second.first]++;
		degree[edges[i].second.second]++;
		uf.unite(edges[i].second.first, edges[i].second.second,
				 degree[edges[i].second.first] >= 3 ||
					 degree[edges[i].second.second] >= 3 ||
					 uf.same(edges[i].second.first, edges[i].second.second));
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int min = -1, max = M;
	while (min + 1 < max) {
		int mid = (min + max) / 2;
		int root_x = uf.find(X, mid), root_y = uf.find(Y, mid);
		if (root_x != root_y) {
			min = mid;
			continue;
		}
		if (uf.ok(root_x, mid))
			max = mid;
		else
			min = mid;
	}
	if (max != M) return edges[max].first;
	return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2252 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 2 ms 2268 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 2288 KB Output is correct
8 Correct 2 ms 2252 KB Output is correct
9 Correct 41 ms 5428 KB Output is correct
10 Correct 50 ms 6060 KB Output is correct
11 Correct 52 ms 6052 KB Output is correct
12 Correct 53 ms 6276 KB Output is correct
13 Correct 72 ms 6688 KB Output is correct
14 Correct 64 ms 5504 KB Output is correct
15 Correct 283 ms 7620 KB Output is correct
16 Correct 297 ms 7608 KB Output is correct
17 Correct 294 ms 7784 KB Output is correct
18 Execution timed out 2075 ms 8232 KB Time limit exceeded

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2252 KB Output is correct
3 Execution timed out 2067 ms 7588 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2252 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 2 ms 2268 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 2 ms 2288 KB Output is correct
9 Correct 2 ms 2252 KB Output is correct
10 Correct 41 ms 5428 KB Output is correct
11 Correct 50 ms 6060 KB Output is correct
12 Correct 52 ms 6052 KB Output is correct
13 Correct 53 ms 6276 KB Output is correct
14 Correct 72 ms 6688 KB Output is correct
15 Correct 3 ms 2252 KB Output is correct
16 Correct 3 ms 2252 KB Output is correct
17 Correct 3 ms 2252 KB Output is correct
18 Correct 2 ms 2252 KB Output is correct
19 Correct 2 ms 2252 KB Output is correct
20 Correct 3 ms 2252 KB Output is correct
21 Correct 3 ms 2252 KB Output is correct
22 Correct 2 ms 2252 KB Output is correct
23 Correct 2 ms 2252 KB Output is correct
24 Correct 2 ms 2252 KB Output is correct
25 Correct 2 ms 2252 KB Output is correct
26 Correct 2 ms 2252 KB Output is correct
27 Correct 3 ms 2252 KB Output is correct
28 Correct 2 ms 2252 KB Output is correct
29 Correct 3 ms 2252 KB Output is correct
30 Correct 3 ms 2380 KB Output is correct
31 Correct 3 ms 2252 KB Output is correct
32 Correct 3 ms 2280 KB Output is correct
33 Correct 3 ms 2252 KB Output is correct
34 Correct 10 ms 2892 KB Output is correct
35 Correct 51 ms 6252 KB Output is correct
36 Correct 50 ms 6212 KB Output is correct
37 Correct 50 ms 6340 KB Output is correct
38 Correct 49 ms 6236 KB Output is correct
39 Correct 51 ms 6112 KB Output is correct
40 Correct 47 ms 5876 KB Output is correct
41 Correct 54 ms 6292 KB Output is correct
42 Correct 50 ms 6248 KB Output is correct
43 Correct 63 ms 6280 KB Output is correct
44 Correct 56 ms 6284 KB Output is correct
45 Correct 84 ms 7808 KB Output is correct
46 Correct 51 ms 6212 KB Output is correct
47 Correct 51 ms 6248 KB Output is correct
48 Correct 63 ms 6624 KB Output is correct
49 Correct 69 ms 7960 KB Output is correct
50 Correct 57 ms 6596 KB Output is correct
51 Correct 71 ms 7100 KB Output is correct
52 Correct 83 ms 8380 KB Output is correct
53 Correct 95 ms 8968 KB Output is correct
54 Correct 101 ms 9796 KB Output is correct
55 Correct 68 ms 6340 KB Output is correct
56 Correct 100 ms 8772 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2252 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 2 ms 2268 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 2288 KB Output is correct
8 Correct 2 ms 2252 KB Output is correct
9 Correct 41 ms 5428 KB Output is correct
10 Correct 50 ms 6060 KB Output is correct
11 Correct 52 ms 6052 KB Output is correct
12 Correct 53 ms 6276 KB Output is correct
13 Correct 72 ms 6688 KB Output is correct
14 Correct 64 ms 5504 KB Output is correct
15 Correct 283 ms 7620 KB Output is correct
16 Correct 297 ms 7608 KB Output is correct
17 Correct 294 ms 7784 KB Output is correct
18 Execution timed out 2075 ms 8232 KB Time limit exceeded

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2252 KB Output is correct
2 Correct 2 ms 2252 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 2 ms 2268 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 2 ms 2288 KB Output is correct
9 Correct 2 ms 2252 KB Output is correct
10 Correct 41 ms 5428 KB Output is correct
11 Correct 50 ms 6060 KB Output is correct
12 Correct 52 ms 6052 KB Output is correct
13 Correct 53 ms 6276 KB Output is correct
14 Correct 72 ms 6688 KB Output is correct
15 Correct 64 ms 5504 KB Output is correct
16 Correct 283 ms 7620 KB Output is correct
17 Correct 297 ms 7608 KB Output is correct
18 Correct 294 ms 7784 KB Output is correct
19 Execution timed out 2075 ms 8232 KB Time limit exceeded