oj.uz

Submission #410189

# Submission time Handle Problem Language Result Execution time Memory
410189 2021-05-22T08:42:34 Z kaage Swapping Cities (APIO20_swap) C++17
37 / 100
 2000 ms 10368 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 - 1) { return ok_vec[x] <= t; }
	int get_opcount() { return opcount; }
};

int N, M;
std::vector<std::pair<int, IP>> edges;
std::vector<int> avail_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]++;
		int X = uf.find(edges[i].second.first),
			Y = uf.find(edges[i].second.second);
		if (X == Y) {
			if (!uf.ok(X)) {
				uf.unite(X, Y, true);
				avail_edges.emplace_back(i);
			}
		} else {
			uf.unite(X, Y,
					 degree[edges[i].second.first] >= 3 ||
						 degree[edges[i].second.second] >= 3);
			avail_edges.emplace_back(i);
		}
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int min = -1, max = avail_edges.size();
	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[avail_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 2252 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 2252 KB Output is correct
8 Correct 2 ms 2252 KB Output is correct
9 Correct 42 ms 5860 KB Output is correct
10 Correct 51 ms 6592 KB Output is correct
11 Correct 67 ms 6576 KB Output is correct
12 Correct 57 ms 6720 KB Output is correct
13 Correct 71 ms 6880 KB Output is correct
14 Correct 63 ms 6080 KB Output is correct
15 Correct 283 ms 8252 KB Output is correct
16 Correct 287 ms 8092 KB Output is correct
17 Correct 290 ms 8292 KB Output is correct
18 Execution timed out 2044 ms 8440 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 2090 ms 7976 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 2252 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 2252 KB Output is correct
8 Correct 2 ms 2252 KB Output is correct
9 Correct 2 ms 2252 KB Output is correct
10 Correct 2 ms 2252 KB Output is correct
11 Correct 2 ms 2252 KB Output is correct
12 Correct 2 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 2 ms 2252 KB Output is correct
16 Correct 2 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 2252 KB Output is correct
26 Correct 3 ms 2252 KB Output is correct
27 Correct 2 ms 2252 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 2252 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 2252 KB Output is correct
9 Correct 2 ms 2252 KB Output is correct
10 Correct 42 ms 5860 KB Output is correct
11 Correct 51 ms 6592 KB Output is correct
12 Correct 67 ms 6576 KB Output is correct
13 Correct 57 ms 6720 KB Output is correct
14 Correct 71 ms 6880 KB Output is correct
15 Correct 2 ms 2252 KB Output is correct
16 Correct 2 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 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 2252 KB Output is correct
31 Correct 3 ms 2252 KB Output is correct
32 Correct 2 ms 2252 KB Output is correct
33 Correct 3 ms 2252 KB Output is correct
34 Correct 9 ms 2892 KB Output is correct
35 Correct 54 ms 6768 KB Output is correct
36 Correct 54 ms 6844 KB Output is correct
37 Correct 52 ms 6752 KB Output is correct
38 Correct 51 ms 6748 KB Output is correct
39 Correct 53 ms 6716 KB Output is correct
40 Correct 49 ms 6384 KB Output is correct
41 Correct 53 ms 6720 KB Output is correct
42 Correct 53 ms 6756 KB Output is correct
43 Correct 63 ms 6756 KB Output is correct
44 Correct 55 ms 6796 KB Output is correct
45 Correct 85 ms 8328 KB Output is correct
46 Correct 52 ms 6740 KB Output is correct
47 Correct 58 ms 6720 KB Output is correct
48 Correct 65 ms 7144 KB Output is correct
49 Correct 72 ms 7748 KB Output is correct
50 Correct 57 ms 6492 KB Output is correct
51 Correct 73 ms 7356 KB Output is correct
52 Correct 86 ms 8872 KB Output is correct
53 Correct 98 ms 9980 KB Output is correct
54 Correct 108 ms 10368 KB Output is correct
55 Correct 67 ms 6756 KB Output is correct
56 Correct 101 ms 9268 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 2252 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 2252 KB Output is correct
8 Correct 2 ms 2252 KB Output is correct
9 Correct 42 ms 5860 KB Output is correct
10 Correct 51 ms 6592 KB Output is correct
11 Correct 67 ms 6576 KB Output is correct
12 Correct 57 ms 6720 KB Output is correct
13 Correct 71 ms 6880 KB Output is correct
14 Correct 63 ms 6080 KB Output is correct
15 Correct 283 ms 8252 KB Output is correct
16 Correct 287 ms 8092 KB Output is correct
17 Correct 290 ms 8292 KB Output is correct
18 Execution timed out 2044 ms 8440 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 2252 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 2252 KB Output is correct
9 Correct 2 ms 2252 KB Output is correct
10 Correct 42 ms 5860 KB Output is correct
11 Correct 51 ms 6592 KB Output is correct
12 Correct 67 ms 6576 KB Output is correct
13 Correct 57 ms 6720 KB Output is correct
14 Correct 71 ms 6880 KB Output is correct
15 Correct 63 ms 6080 KB Output is correct
16 Correct 283 ms 8252 KB Output is correct
17 Correct 287 ms 8092 KB Output is correct
18 Correct 290 ms 8292 KB Output is correct
19 Execution timed out 2044 ms 8440 KB Time limit exceeded