This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/int_alias.hpp"
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 6 "library2/utility/priority_sort.hpp"
namespace magic {
template <class T, class... Tail>
void priority_sort_renumber(const std::vector<int> &order, std::vector<T> &head, Tail &...tail) {
const int n = len(order);
std::vector<T> sorted_head(n);
for (int i = 0; i < n; ++i) {
sorted_head[i] = head[order[i]];
}
head = std::move(sorted_head);
if constexpr (sizeof...(Tail) != 0) {
priority_sort_renumber(order, tail...);
}
}
} // namespace magic
template <class Head, class... Tail>
std::vector<int> priority_sort(std::vector<Head> &head, std::vector<Tail> &...tail) {
const int n = len(head);
std::vector<std::tuple<Head, Tail..., int>> res(n);
for (int i = 0; i < n; ++i) {
res[i] = std::make_tuple(head[i], tail[i]..., i);
}
std::sort(res.begin(), res.end());
std::vector<int> order(n);
for (int i = 0; i < n; ++i) {
order[i] = std::get<std::tuple_size_v<std::tuple<Head, Tail...>>>(res[i]);
}
magic::priority_sort_renumber(order, head, tail...);
return order;
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 6 "paper.cpp"
class BubunEizokuUnionFindKaizou {
int n;
struct Node {
int parent;
int size;
int deg1;
int deg2;
int deg3;
bool cycle;
};
std::vector<Node> now_data;
std::vector<i64> last_time;
std::vector<std::vector<std::pair<i64, Node>>> history;
std::vector<int> degree;
std::vector<std::vector<std::pair<i64, int>>> deg_history;
public:
BubunEizokuUnionFindKaizou() = default;
BubunEizokuUnionFindKaizou(const int n_) : n(n_) {
now_data.resize(n);
history.resize(n);
for (const int i : rep(n)) {
now_data[i] = {i, 1, 0, 0};
history[i].push_back({0, {i, 1, 0, 0, 0, false}});
}
degree.assign(n, 0);
last_time.assign(n, -1);
deg_history.resize(n);
for (const int i : rep(n)) {
deg_history[i].push_back({0, 0});
}
}
bool same(int a, int b, i64 t) {
return root(a, t) == root(b, t);
}
int root(int v, i64 t) {
if (last_time[v] == -1 or t < last_time[v]) {
return v;
} else {
return root(now_data[v].parent, t);
}
}
void unite(int a, int b, i64 c) {
int ra = root(a, c), rb = root(b, c);
if (ra == rb) {
now_data[ra].cycle = true;
if (degree[a] <= 3) {
if (degree[a] == 0) {
++now_data[ra].deg1;
}
if (degree[a] == 1) {
--now_data[ra].deg1;
++now_data[ra].deg2;
}
if (degree[a] == 2) {
--now_data[ra].deg2;
++now_data[ra].deg3;
}
if (degree[a] == 3) {
--now_data[ra].deg3;
}
}
if (degree[b] <= 3) {
if (degree[b] == 0) {
++now_data[ra].deg1;
}
if (degree[b] == 1) {
--now_data[ra].deg1;
++now_data[ra].deg2;
}
if (degree[b] == 2) {
--now_data[ra].deg2;
++now_data[ra].deg3;
}
}
++degree[a];
++degree[b];
history[ra].push_back({c, now_data[ra]});
} else {
if (now_data[ra].size < now_data[rb].size) {
std::swap(a, b);
std::swap(ra, rb);
}
now_data[ra].size += now_data[rb].size;
now_data[rb].parent = ra;
now_data[ra].deg1 += now_data[rb].deg1;
now_data[ra].deg2 += now_data[rb].deg2;
now_data[ra].deg3 += now_data[rb].deg3;
now_data[ra].cycle |= now_data[rb].cycle;
last_time[rb] = c;
if (degree[a] <= 2) {
if (degree[a] == 0) {
++now_data[ra].deg1;
}
if (degree[a] == 1) {
--now_data[ra].deg1;
++now_data[ra].deg2;
}
if (degree[a] == 2) {
--now_data[ra].deg2;
++now_data[ra].deg3;
}
}
if (degree[b] <= 2) {
if (degree[b] == 0) {
++now_data[ra].deg1;
}
if (degree[b] == 1) {
--now_data[ra].deg1;
++now_data[ra].deg2;
}
if (degree[b] == 2) {
--now_data[ra].deg2;
++now_data[ra].deg3;
}
}
++degree[a];
++degree[b];
deg_history[a].push_back({c, degree[a]});
deg_history[b].push_back({c, degree[b]});
history[ra].push_back({c, now_data[ra]});
}
}
int deg(int v, i64 t) {
return (--std::upper_bound(deg_history[v].begin(), deg_history[v].end(),
std::make_pair(t, 1000000001)))
->second;
}
Node view(int v, i64 t) {
v = root(v, t);
return (--std::upper_bound(history[v].begin(), history[v].end(), std::make_pair(t, 0),
[](auto a, auto b) { return a.first < b.first; }))
->second;
}
};
int N, M;
std::vector<int> U, V, W;
BubunEizokuUnionFindKaizou uft;
void init(int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> w) {
N = n;
M = m;
U = u;
V = v;
W = w;
uft = BubunEizokuUnionFindKaizou(N);
priority_sort(W, U, V);
for (const int i : rep(M)) {
uft.unite(U[i], V[i], W[i]);
}
}
int getMinimumFuelCapacity(int X, int Y) {
if (not uft.same(X, Y, 1000000001)) {
return -1;
}
const auto bestnode = uft.view(X, 1000000001);
if ((not bestnode.cycle) and (bestnode.deg3 == 0)) {
return -1;
}
int ok = 1000000001, ng = -1;
while (ok - ng > 1) {
const auto mid = (ok + ng) / 2;
if (not uft.same(X, Y, mid)) {
ng = mid;
} else {
const auto node = uft.view(X, mid);
if ((not node.cycle) and (node.deg3 == 0)) {
ng = mid;
} else {
ok = mid;
}
}
}
return ok;
}
/*
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
}
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
assert(2 == scanf("%d %d", &X[i], &Y[i]));
}
init(N, M, U, V, W);
std::vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i) {
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i) {
printf("%d\n", minimum_fuel_capacities[i]);
}
return 0;
}
*/
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
