Submission #410183

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410183	2021-05-22T08:15:09 Z	kaage	Swapping Cities (APIO20_swap)	C++17	37 / 100	2000 ms	20308 KB

swap

#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<std::vector<std::pair<int, int>>> sizevec;
	std::vector<int> ok_vec;
	int opcount = 0;

  public:
	PersistentUnionFind(unsigned int size) : UnionFind(size) {
		notparent.resize(size);
		sizevec.resize(size);
		ok_vec.resize(size, INF);
		rep(i, size) {
			par[i] = i;
			sizevec[i].push_back(std::make_pair(-1, 1));
			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;

		sizevec[m].emplace_back(
			opcount, sizevec[m].back().second + sizevec[n].back().second);
		opcount++;
	}
	bool same(int n, int m, int t = INF) { return find(n, t) == find(m, t); }
	int getsize(int n, int t = INF) {
		n = find(n, t);
		auto ite = std::lower_bound(all(sizevec[n]), std::make_pair(t, 0));
		if (ite == sizevec[n].end()) ite--;
		if (t < (*ite).first) ite--;
		return (*ite).second;
	}
	bool ok(int x, int t = INF) { return ok_vec[find(x, t)] <= 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;
	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	9 ms	7628 KB	Output is correct
2	Correct	9 ms	7628 KB	Output is correct
3	Correct	9 ms	7652 KB	Output is correct
4	Correct	9 ms	7756 KB	Output is correct
5	Correct	10 ms	7756 KB	Output is correct
6	Correct	10 ms	7756 KB	Output is correct
7	Correct	10 ms	7756 KB	Output is correct
8	Correct	10 ms	7756 KB	Output is correct
9	Correct	65 ms	11724 KB	Output is correct
10	Correct	78 ms	12572 KB	Output is correct
11	Correct	77 ms	12556 KB	Output is correct
12	Correct	90 ms	12876 KB	Output is correct
13	Correct	98 ms	13120 KB	Output is correct
14	Correct	88 ms	11852 KB	Output is correct
15	Correct	315 ms	14412 KB	Output is correct
16	Correct	318 ms	14380 KB	Output is correct
17	Correct	316 ms	14548 KB	Output is correct
18	Execution timed out	2081 ms	14900 KB	Time limit exceeded

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7628 KB	Output is correct
2	Correct	9 ms	7628 KB	Output is correct
3	Execution timed out	2064 ms	13068 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7628 KB	Output is correct
2	Correct	9 ms	7628 KB	Output is correct
3	Correct	9 ms	7652 KB	Output is correct
4	Correct	9 ms	7756 KB	Output is correct
5	Correct	10 ms	7756 KB	Output is correct
6	Correct	10 ms	7756 KB	Output is correct
7	Correct	10 ms	7756 KB	Output is correct
8	Correct	10 ms	7756 KB	Output is correct
9	Correct	10 ms	7712 KB	Output is correct
10	Correct	12 ms	7760 KB	Output is correct
11	Correct	10 ms	7756 KB	Output is correct
12	Correct	9 ms	7756 KB	Output is correct
13	Correct	12 ms	7792 KB	Output is correct
14	Correct	14 ms	7776 KB	Output is correct
15	Correct	9 ms	7756 KB	Output is correct
16	Correct	9 ms	7752 KB	Output is correct
17	Correct	10 ms	7764 KB	Output is correct
18	Correct	10 ms	7732 KB	Output is correct
19	Correct	10 ms	7756 KB	Output is correct
20	Correct	10 ms	7756 KB	Output is correct
21	Correct	11 ms	7756 KB	Output is correct
22	Correct	11 ms	7768 KB	Output is correct
23	Correct	10 ms	7756 KB	Output is correct
24	Correct	13 ms	7756 KB	Output is correct
25	Correct	10 ms	7756 KB	Output is correct
26	Correct	10 ms	7756 KB	Output is correct
27	Correct	10 ms	7756 KB	Output is correct
28	Correct	10 ms	7756 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	7712 KB	Output is correct
2	Correct	9 ms	7628 KB	Output is correct
3	Correct	9 ms	7628 KB	Output is correct
4	Correct	9 ms	7652 KB	Output is correct
5	Correct	9 ms	7756 KB	Output is correct
6	Correct	10 ms	7756 KB	Output is correct
7	Correct	10 ms	7756 KB	Output is correct
8	Correct	10 ms	7756 KB	Output is correct
9	Correct	10 ms	7756 KB	Output is correct
10	Correct	65 ms	11724 KB	Output is correct
11	Correct	78 ms	12572 KB	Output is correct
12	Correct	77 ms	12556 KB	Output is correct
13	Correct	90 ms	12876 KB	Output is correct
14	Correct	98 ms	13120 KB	Output is correct
15	Correct	12 ms	7760 KB	Output is correct
16	Correct	10 ms	7756 KB	Output is correct
17	Correct	9 ms	7756 KB	Output is correct
18	Correct	12 ms	7792 KB	Output is correct
19	Correct	14 ms	7776 KB	Output is correct
20	Correct	9 ms	7756 KB	Output is correct
21	Correct	9 ms	7752 KB	Output is correct
22	Correct	10 ms	7764 KB	Output is correct
23	Correct	10 ms	7732 KB	Output is correct
24	Correct	10 ms	7756 KB	Output is correct
25	Correct	10 ms	7756 KB	Output is correct
26	Correct	11 ms	7756 KB	Output is correct
27	Correct	11 ms	7768 KB	Output is correct
28	Correct	10 ms	7756 KB	Output is correct
29	Correct	13 ms	7756 KB	Output is correct
30	Correct	10 ms	7756 KB	Output is correct
31	Correct	10 ms	7756 KB	Output is correct
32	Correct	10 ms	7756 KB	Output is correct
33	Correct	10 ms	7756 KB	Output is correct
34	Correct	17 ms	8652 KB	Output is correct
35	Correct	84 ms	14636 KB	Output is correct
36	Correct	82 ms	14660 KB	Output is correct
37	Correct	79 ms	14644 KB	Output is correct
38	Correct	80 ms	14556 KB	Output is correct
39	Correct	79 ms	14488 KB	Output is correct
40	Correct	76 ms	13896 KB	Output is correct
41	Correct	88 ms	14912 KB	Output is correct
42	Correct	85 ms	14560 KB	Output is correct
43	Correct	90 ms	14640 KB	Output is correct
44	Correct	83 ms	14812 KB	Output is correct
45	Correct	113 ms	17600 KB	Output is correct
46	Correct	80 ms	14644 KB	Output is correct
47	Correct	79 ms	14612 KB	Output is correct
48	Correct	88 ms	15152 KB	Output is correct
49	Correct	79 ms	17388 KB	Output is correct
50	Correct	66 ms	14532 KB	Output is correct
51	Correct	89 ms	15900 KB	Output is correct
52	Correct	116 ms	18316 KB	Output is correct
53	Correct	125 ms	19384 KB	Output is correct
54	Correct	132 ms	20308 KB	Output is correct
55	Correct	96 ms	14648 KB	Output is correct
56	Correct	128 ms	18952 KB	Output is correct

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7628 KB	Output is correct
2	Correct	9 ms	7628 KB	Output is correct
3	Correct	9 ms	7652 KB	Output is correct
4	Correct	9 ms	7756 KB	Output is correct
5	Correct	10 ms	7756 KB	Output is correct
6	Correct	10 ms	7756 KB	Output is correct
7	Correct	10 ms	7756 KB	Output is correct
8	Correct	10 ms	7756 KB	Output is correct
9	Correct	65 ms	11724 KB	Output is correct
10	Correct	78 ms	12572 KB	Output is correct
11	Correct	77 ms	12556 KB	Output is correct
12	Correct	90 ms	12876 KB	Output is correct
13	Correct	98 ms	13120 KB	Output is correct
14	Correct	88 ms	11852 KB	Output is correct
15	Correct	315 ms	14412 KB	Output is correct
16	Correct	318 ms	14380 KB	Output is correct
17	Correct	316 ms	14548 KB	Output is correct
18	Execution timed out	2081 ms	14900 KB	Time limit exceeded

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	7712 KB	Output is correct
2	Correct	9 ms	7628 KB	Output is correct
3	Correct	9 ms	7628 KB	Output is correct
4	Correct	9 ms	7652 KB	Output is correct
5	Correct	9 ms	7756 KB	Output is correct
6	Correct	10 ms	7756 KB	Output is correct
7	Correct	10 ms	7756 KB	Output is correct
8	Correct	10 ms	7756 KB	Output is correct
9	Correct	10 ms	7756 KB	Output is correct
10	Correct	65 ms	11724 KB	Output is correct
11	Correct	78 ms	12572 KB	Output is correct
12	Correct	77 ms	12556 KB	Output is correct
13	Correct	90 ms	12876 KB	Output is correct
14	Correct	98 ms	13120 KB	Output is correct
15	Correct	88 ms	11852 KB	Output is correct
16	Correct	315 ms	14412 KB	Output is correct
17	Correct	318 ms	14380 KB	Output is correct
18	Correct	316 ms	14548 KB	Output is correct
19	Execution timed out	2081 ms	14900 KB	Time limit exceeded