oj.uz

답안 #410173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410173 2021-05-22T07:07:38 Z kaage 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 19120 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<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 (f) chmin(ok_vec[m], opcount);
		chmin(ok_vec[m], ok_vec[n]);

		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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7628 KB Output is correct
2 Correct 10 ms 7752 KB Output is correct
3 Correct 10 ms 7752 KB Output is correct
4 Correct 11 ms 7684 KB Output is correct
5 Correct 10 ms 7756 KB Output is correct
6 Correct 10 ms 7728 KB Output is correct
7 Correct 10 ms 7756 KB Output is correct
8 Correct 10 ms 7764 KB Output is correct
9 Correct 66 ms 13324 KB Output is correct
10 Correct 80 ms 14652 KB Output is correct
11 Correct 78 ms 14464 KB Output is correct
12 Correct 82 ms 14892 KB Output is correct
13 Correct 105 ms 15288 KB Output is correct
14 Correct 89 ms 13756 KB Output is correct
15 Correct 319 ms 18836 KB Output is correct
16 Correct 324 ms 18796 KB Output is correct
17 Correct 321 ms 18960 KB Output is correct
18 Execution timed out 2039 ms 19120 KB Time limit exceeded

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7628 KB Output is correct
2 Correct 10 ms 7752 KB Output is correct
3 Execution timed out 2077 ms 16892 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7628 KB Output is correct
2 Correct 10 ms 7752 KB Output is correct
3 Correct 10 ms 7752 KB Output is correct
4 Correct 11 ms 7684 KB Output is correct
5 Correct 10 ms 7756 KB Output is correct
6 Correct 10 ms 7728 KB Output is correct
7 Correct 10 ms 7756 KB Output is correct
8 Correct 10 ms 7764 KB Output is correct
9 Correct 9 ms 7676 KB Output is correct
10 Correct 10 ms 7756 KB Output is correct
11 Correct 10 ms 7800 KB Output is correct
12 Correct 10 ms 7756 KB Output is correct
13 Correct 10 ms 7756 KB Output is correct
14 Correct 10 ms 7768 KB Output is correct
15 Correct 10 ms 7700 KB Output is correct
16 Correct 10 ms 7720 KB Output is correct
17 Correct 10 ms 7756 KB Output is correct
18 Correct 10 ms 7756 KB Output is correct
19 Correct 10 ms 7764 KB Output is correct
20 Correct 10 ms 7756 KB Output is correct
21 Correct 11 ms 7804 KB Output is correct
22 Correct 11 ms 7756 KB Output is correct
23 Correct 10 ms 7756 KB Output is correct
24 Incorrect 10 ms 7752 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7676 KB Output is correct
2 Correct 9 ms 7628 KB Output is correct
3 Correct 10 ms 7752 KB Output is correct
4 Correct 10 ms 7752 KB Output is correct
5 Correct 11 ms 7684 KB Output is correct
6 Correct 10 ms 7756 KB Output is correct
7 Correct 10 ms 7728 KB Output is correct
8 Correct 10 ms 7756 KB Output is correct
9 Correct 10 ms 7764 KB Output is correct
10 Correct 66 ms 13324 KB Output is correct
11 Correct 80 ms 14652 KB Output is correct
12 Correct 78 ms 14464 KB Output is correct
13 Correct 82 ms 14892 KB Output is correct
14 Correct 105 ms 15288 KB Output is correct
15 Correct 10 ms 7756 KB Output is correct
16 Correct 10 ms 7800 KB Output is correct
17 Correct 10 ms 7756 KB Output is correct
18 Correct 10 ms 7756 KB Output is correct
19 Correct 10 ms 7768 KB Output is correct
20 Correct 10 ms 7700 KB Output is correct
21 Correct 10 ms 7720 KB Output is correct
22 Correct 10 ms 7756 KB Output is correct
23 Correct 10 ms 7756 KB Output is correct
24 Correct 10 ms 7764 KB Output is correct
25 Correct 10 ms 7756 KB Output is correct
26 Correct 11 ms 7804 KB Output is correct
27 Correct 11 ms 7756 KB Output is correct
28 Correct 10 ms 7756 KB Output is correct
29 Incorrect 10 ms 7752 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7628 KB Output is correct
2 Correct 10 ms 7752 KB Output is correct
3 Correct 10 ms 7752 KB Output is correct
4 Correct 11 ms 7684 KB Output is correct
5 Correct 10 ms 7756 KB Output is correct
6 Correct 10 ms 7728 KB Output is correct
7 Correct 10 ms 7756 KB Output is correct
8 Correct 10 ms 7764 KB Output is correct
9 Correct 66 ms 13324 KB Output is correct
10 Correct 80 ms 14652 KB Output is correct
11 Correct 78 ms 14464 KB Output is correct
12 Correct 82 ms 14892 KB Output is correct
13 Correct 105 ms 15288 KB Output is correct
14 Correct 89 ms 13756 KB Output is correct
15 Correct 319 ms 18836 KB Output is correct
16 Correct 324 ms 18796 KB Output is correct
17 Correct 321 ms 18960 KB Output is correct
18 Execution timed out 2039 ms 19120 KB Time limit exceeded

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7676 KB Output is correct
2 Correct 9 ms 7628 KB Output is correct
3 Correct 10 ms 7752 KB Output is correct
4 Correct 10 ms 7752 KB Output is correct
5 Correct 11 ms 7684 KB Output is correct
6 Correct 10 ms 7756 KB Output is correct
7 Correct 10 ms 7728 KB Output is correct
8 Correct 10 ms 7756 KB Output is correct
9 Correct 10 ms 7764 KB Output is correct
10 Correct 66 ms 13324 KB Output is correct
11 Correct 80 ms 14652 KB Output is correct
12 Correct 78 ms 14464 KB Output is correct
13 Correct 82 ms 14892 KB Output is correct
14 Correct 105 ms 15288 KB Output is correct
15 Correct 89 ms 13756 KB Output is correct
16 Correct 319 ms 18836 KB Output is correct
17 Correct 324 ms 18796 KB Output is correct
18 Correct 321 ms 18960 KB Output is correct
19 Execution timed out 2039 ms 19120 KB Time limit exceeded