// #define MULTEST
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>
namespace kod {
namespace util {
template <class F> class FixedPoint : private F {
constexpr FixedPoint(F&& f) noexcept : F(std::forward<F>(f)) {}
template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;
public:
template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
using F = std::decay_t<G>;
return FixedPoint<F>(std::forward<F>(g));
}
} // namespace util
} // namespace kod
namespace kod {
namespace util {
class ForwardLoop {
int x, y;
constexpr ForwardLoop(int x, int y) noexcept : x(x), y(y) {}
friend constexpr ForwardLoop rep(int, int) noexcept;
friend constexpr ForwardLoop rep(int) noexcept;
public:
constexpr ForwardLoop begin() const noexcept { return *this; }
constexpr std::monostate end() const noexcept { return {}; }
constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
constexpr void operator++() const noexcept {}
constexpr int operator*() noexcept { return x++; }
};
[[nodiscard]] constexpr ForwardLoop rep(int l, int r) noexcept { return ForwardLoop(l, r); }
[[nodiscard]] constexpr ForwardLoop rep(int n) noexcept { return ForwardLoop(0, n); }
class BackwardLoop {
int x, y;
constexpr BackwardLoop(int x, int y) noexcept : x(x), y(y) {}
friend constexpr BackwardLoop revrep(int, int) noexcept;
friend constexpr BackwardLoop revrep(int) noexcept;
public:
constexpr BackwardLoop begin() const noexcept { return *this; }
constexpr std::monostate end() const noexcept { return {}; }
constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
constexpr void operator++() const noexcept {}
constexpr int operator*() noexcept { return --x; }
};
[[nodiscard]] constexpr BackwardLoop revrep(int l, int r) noexcept { return BackwardLoop(r, l); }
[[nodiscard]] constexpr BackwardLoop revrep(int n) noexcept { return BackwardLoop(n, 0); }
template <class F> constexpr void repeat(int n, const F& f) noexcept {
assert(n >= 0);
while (n--) f();
}
} // namespace util
} // namespace kod
namespace kod {
namespace util {
namespace stdio_impl {
template <class T> T scan() {
T x;
std::cin >> x;
return x;
}
struct scan_any {
template <class T> operator T() const { return scan<T>(); }
};
} // namespace stdio_impl
template <class T = void> decltype(auto) scan() {
if constexpr (std::is_same_v<T, void>)
return stdio_impl::scan_any{};
else
return stdio_impl::scan<T>();
}
template <class T, std::size_t N> std::array<T, N> scan_arr() {
std::array<T, N> a;
for (auto& x : a) x = scan<T>();
return a;
}
template <class T> std::vector<T> scan_vec(int n) {
if (n == -1) n = scan<int>();
assert(n >= 0);
std::vector<T> v;
v.reserve(n);
while (n--) v.push_back(scan<T>());
return v;
}
void flush() { std::cout << std::flush; }
void print() {}
template <class T, class... Args> void print(const T& x, const Args&... args) {
std::cout << x;
if (sizeof...(args) != 0) std::cout << ' ';
print(args...);
}
template <class... Args> void println(const Args&... args) {
print(args...);
std::cout << '\n';
}
template <class C> void print_seq(const C& c, const char* sep = " ", const char* end = "\n") {
bool f = false;
for (const auto& x : c) {
if (f)
std::cout << sep;
else
f = true;
std::cout << x;
}
std::cout << end;
}
} // namespace util
} // namespace kod
namespace kod {
namespace sol {
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using namespace util;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;
constexpr ll floor_div(ll x, ll y) noexcept {
assert(y != 0);
return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
assert(y != 0);
return x / y + ((x ^ y) >= 0 && x % y != 0);
}
template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
void run();
} // namespace sol
} // namespace kod
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(20);
int cases = 1;
#ifdef MULTEST
std::cin >> cases;
#endif
while (cases--) kod::sol::run();
return 0;
}
#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif
namespace kod {
namespace sol {
namespace proconlib {
template <class T> class SimpleQueue {
std::vector<T> payload;
int pos;
public:
SimpleQueue() : payload(), pos(0) {}
explicit SimpleQueue(const int n) : SimpleQueue() { reserve(n); }
int size() const { return (int)payload.size() - pos; }
bool empty() const { return size() == 0; }
T& front() { return payload[pos]; }
void push(const T& t) { payload.push_back(t); }
void push(T&& t) { payload.push_back(std::move(t)); }
void pop() { pos++; }
void reserve(int n) { payload.reserve(n); }
void clear() {
payload.clear();
pos = 0;
}
};
} // namespace proconlib
class IndexOffset {
int offset, len;
public:
constexpr IndexOffset() noexcept : offset(), len() {}
explicit constexpr IndexOffset(const int o, const int l) noexcept : offset(o), len(l) {}
constexpr int size() const { return len; }
constexpr int operator[](const int i) const noexcept {
assert(i < len);
return offset + i;
}
constexpr int to_idx(const int i) const noexcept {
assert(offset <= i and i < offset + len);
return i - offset;
}
};
template <class F> struct RecursiveLambda : private F {
explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F&& f) {
return RecursiveLambda<F>(std::forward<F>(f));
}
class Range {
struct Iter {
int itr;
constexpr Iter(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr int operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr Range(const int first, const int last) noexcept
: first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter 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); }
template <class Flow, std::enable_if_t<std::is_integral_v<Flow>>* = nullptr> class Dinic {
public:
struct Edge {
int src, dst;
Flow flow, cap;
};
private:
int node_count;
std::vector<Edge> graph;
public:
Dinic() : node_count(0), graph() {}
explicit Dinic(const int n) : node_count(n), graph() {}
int size() const { return node_count; }
int edge_count() const { return graph.size(); }
int add_vertex() { return node_count++; }
IndexOffset add_vertices(const int n) {
assert(n >= 0);
const IndexOffset ret(size(), n);
node_count += n;
return ret;
}
const Edge& get_edge(const int i) const {
assert(0 <= i and i < edge_count());
return graph[i];
}
int add_edge(const int src, const int dst, const Flow& cap) {
assert(0 <= src and src < size());
assert(0 <= dst and dst < size());
assert(cap >= 0);
graph.push_back(Edge{src, dst, 0, cap});
return edge_count() - 1;
}
Flow flow(const int src, const int dst) {
return flow(src, dst, std::numeric_limits<Flow>::max());
}
Flow flow(const int src, const int dst, const Flow& flow_limit) {
assert(0 <= src and src < size());
assert(0 <= dst and dst < size());
assert(src != dst);
const int n = size();
const int m = edge_count();
struct E {
int dst, rev;
Flow cap;
};
std::vector<E> edge(2 * m);
std::vector<int> start(n + 1), eidx(m);
{
std::vector<int> deg(n), reidx(m);
for (const int i : rep(m)) {
eidx[i] = deg[graph[i].src]++;
reidx[i] = deg[graph[i].dst]++;
}
for (const int i : rep(n)) start[i + 1] = start[i] + deg[i];
for (const int i : rep(m)) {
const auto& e = graph[i];
const int u = e.src, v = e.dst;
eidx[i] += start[u];
reidx[i] += start[v];
edge[eidx[i]] = {v, reidx[i], e.cap - e.flow};
edge[reidx[i]] = {u, eidx[i], e.flow};
}
}
std::vector<int> level(n), iter(n);
proconlib::SimpleQueue<int> que;
const auto bfs = [&] {
std::fill(level.begin(), level.end(), n);
level[src] = 0;
while (!que.empty()) que.pop();
que.push(src);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (const int i : rep(start[u], start[u + 1])) {
const auto& e = edge[i];
if (e.cap == 0 or level[e.dst] < n) continue;
level[e.dst] = level[u] + 1;
if (e.dst == dst) return;
que.push(e.dst);
}
}
};
const auto dfs = rec_lambda([&](auto&& dfs, const int u, const Flow& ub) -> Flow {
if (u == src) return ub;
Flow ret = 0;
for (int& i = iter[u]; i < start[u + 1]; i += 1) {
auto& e = edge[i];
auto& re = edge[e.rev];
if (level[u] <= level[e.dst] or re.cap == 0) continue;
const Flow d = dfs(e.dst, std::min(ub - ret, re.cap));
if (d == 0) continue;
e.cap += d;
re.cap -= d;
ret += d;
if (ret == ub) return ret;
}
level[u] = n;
return ret;
});
Flow ret = 0;
while (ret < flow_limit) {
bfs();
if (level[dst] == n) break;
std::copy(start.begin(), start.begin() + n, iter.begin());
const Flow f = dfs(dst, flow_limit - ret);
if (f == 0) break;
ret += f;
}
for (const int i : rep(m)) graph[i].flow = graph[i].cap - edge[eidx[i]].cap;
return ret;
}
std::vector<char> min_cut(const int src) const {
assert(0 <= src and src < size());
const int n = size();
std::vector<std::vector<int>> adj(n);
for (const auto& e : graph) {
if (e.flow < e.cap) adj[e.src].push_back(e.dst);
if (e.flow > 0) adj[e.dst].push_back(e.src);
}
std::vector<char> ret(n);
proconlib::SimpleQueue<int> que;
que.push(src);
ret[src] = true;
while (!que.empty()) {
const int u = que.front();
que.pop();
for (const int v : adj[u]) {
if (!ret[v]) {
ret[v] = true;
que.push(v);
}
}
}
return ret;
}
};
void run() {
const int N = scan();
vector<vector<int>> G(N);
for (const int i : rep(N - 1)) {
const int a = scan<int>() - 1;
const int b = scan<int>() - 1;
G[a].push_back(b);
G[b].push_back(a);
}
vector<int> par(N), dep(N);
make_fixed([&](auto&& dfs, const int u) -> void {
for (const int v : G[u]) {
if (par[u] == v) continue;
par[v] = u;
dep[v] = dep[u] + 1;
dfs(v);
}
})(0);
constexpr int log = 17;
array<vector<int>, log> lift = {};
lift[0] = par;
for (const int k : rep(log - 1)) {
lift[k + 1].resize(N);
for (const int i : rep(N)) {
lift[k + 1][i] = lift[k][lift[k][i]];
}
}
const auto lca = [&](int u, int v) {
if (dep[u] < dep[v]) std::swap(u, v);
const int dif = dep[u] - dep[v];
for (const int k : rep(log)) {
if (dif >> k & 1) u = lift[k][u];
}
if (u == v) return u;
for (const int k : revrep(log)) {
if (lift[k][u] != lift[k][v]) {
u = lift[k][u];
v = lift[k][v];
}
}
return par[u];
};
const int M = scan();
vector<int> val(N);
array<vector<int>, log> min, max;
min.fill(vector(N, -1));
max.fill(vector(N, -1));
const auto min_comp = [&](const int i, const int j) {
if (i == -1) return j;
if (j == -1) return i;
return val[i] < val[j] ? j : i;
};
const auto max_comp = [&](const int i, const int j) {
if (i == -1) return j;
if (j == -1) return i;
return val[i] > val[j] ? j : i;
};
for (const int i : rep(M)) {
const char c = scan();
const int u = scan<int>() - 1;
const int v = scan<int>() - 1;
const int w = lca(u, v);
val[i] = scan();
for (int x : {u, v}) {
const int d = dep[x] - dep[w];
for (const int k : rep(log)) {
if (d >> k & 1) {
if (c == 'm') {
min[k][x] = min_comp(min[k][x], i);
} else {
max[k][x] = max_comp(max[k][x], i);
}
x = lift[k][x];
}
}
}
}
for (const int k : revrep(log - 1)) {
for (const int i : rep(N)) {
const int j = lift[k][i];
for (const int x : {i, j}) {
min[k][x] = min_comp(min[k][x], min[k + 1][i]);
max[k][x] = max_comp(max[k][x], max[k + 1][i]);
}
}
}
const auto& lowb = min[0];
const auto& uppb = max[0];
Dinic<int> dinic;
const auto node = dinic.add_vertices(N);
const auto query = dinic.add_vertices(M);
const int src = dinic.add_vertex();
const int dst = dinic.add_vertex();
for (const int i : rep(N)) {
dinic.add_edge(src, node[i], 1);
}
for (const int i : rep(M)) {
dinic.add_edge(query[i], dst, 1);
}
vector<int> eid;
for (const int i : rep(1, N)) {
if (lowb[i] != -1) {
const int e = dinic.add_edge(node[i], query[lowb[i]], 1);
eid.push_back(e);
}
if (uppb[i] != -1) {
const int e = dinic.add_edge(node[i], query[uppb[i]], 1);
eid.push_back(e);
}
}
const int F = dinic.flow(src, dst);
assert(M == F);
vector<int> ans(N);
for (const int i : eid) {
const auto& e = dinic.get_edge(i);
if (e.flow == 1) {
ans[node.to_idx(e.src)] = val[query.to_idx(e.dst)];
}
}
for (const int i : rep(1, N)) {
println(i + 1, par[i] + 1, ans[i]);
}
}
} // namespace sol
} // namespace kod
Compilation message
minmaxtree.cpp: In function 'void kod::sol::run()':
minmaxtree.cpp:453:20: warning: unused variable 'i' [-Wunused-variable]
453 | for (const int i : rep(N - 1)) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
32924 KB |
Output is correct |
| 2 |
Correct |
149 ms |
30816 KB |
Output is correct |
| 3 |
Correct |
130 ms |
31432 KB |
Output is correct |
| 4 |
Correct |
165 ms |
33204 KB |
Output is correct |
| 5 |
Correct |
144 ms |
31408 KB |
Output is correct |
| 6 |
Correct |
108 ms |
31704 KB |
Output is correct |
| 7 |
Correct |
121 ms |
31024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
29260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
118 ms |
32924 KB |
Output is correct |
| 6 |
Correct |
149 ms |
30816 KB |
Output is correct |
| 7 |
Correct |
130 ms |
31432 KB |
Output is correct |
| 8 |
Correct |
165 ms |
33204 KB |
Output is correct |
| 9 |
Correct |
144 ms |
31408 KB |
Output is correct |
| 10 |
Correct |
108 ms |
31704 KB |
Output is correct |
| 11 |
Correct |
121 ms |
31024 KB |
Output is correct |
| 12 |
Incorrect |
89 ms |
29260 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
