| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 988531 |
2024-05-25T06:07:12 Z |
AC2K |
Regions (IOI09_regions) |
C++17 |
|
296 ms |
131072 KB |
#line 1 "Library/src/debug.hpp"
#ifdef ONLINE_JUDGE
#define debug(x) void(0)
#else
#define _GLIBCXX_DEBUG
#define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl
#endif
/**
* @brief Debugger
*/
#line 2 "Library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 2 "Library/src/internal/type_traits.hpp"
#include <iostream>
#include <limits>
#include <numeric>
#include <typeinfo>
#include <cstdint>
namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
: first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
using type = T;
};
template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
std::enable_if<dgt <= 16, std::int16_t>,
std::enable_if<dgt <= 32, std::int32_t>,
std::enable_if<dgt <= 64, std::int64_t>,
std::enable_if<dgt <= 128, __int128_t>>;
};
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
std::enable_if<dgt <= 16, std::uint16_t>,
std::enable_if<dgt <= 32, std::uint32_t>,
std::enable_if<dgt <= 64, std::uint64_t>,
std::enable_if<dgt <= 128, __uint128_t>>;
};
template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;
template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;
template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;
struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
// is_integral
template <typename T>
using is_integral_t =
std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
std::is_same_v<T, __uint128_t>>;
}; // namespace internal
}; // namespace kyopro
/**
* @brief Type Traits
* @see https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
*/
#line 6 "Library/src/stream.hpp"
namespace kyopro {
inline void single_read(char& c) {
c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_read(T& a) {
a = 0;
bool is_negative = false;
char c = getchar_unlocked();
while (isspace(c)) {
c = getchar_unlocked();
}
if (c == '-') is_negative = true, c = getchar_unlocked();
while (isdigit(c)) {
a = 10 * a + (c - '0');
c = getchar_unlocked();
}
if (is_negative) a *= -1;
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_read(T& a) {
long long x;
single_read(x);
a = T(x);
}
inline void single_read(std::string& str) noexcept {
char c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
while (!isspace(c)) {
str += c;
c = getchar_unlocked();
}
}
template<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
single_read(head), read(tail...);
}
inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
if (!a) {
putchar_unlocked('0');
return;
}
if constexpr (std::is_signed_v<T>) {
if (a < 0) putchar_unlocked('-'), a *= -1;
}
constexpr int d = std::numeric_limits<T>::digits10;
char s[d + 1];
int now = d + 1;
while (a) {
s[--now] = (char)'0' + a % 10;
a /= 10;
}
while (now <= d) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_write(T a) noexcept {
single_write(a.val());
}
inline void single_write(const std::string& str) noexcept {
for (auto c : str) {
putchar_unlocked(c);
}
}
template <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
single_write(head);
putchar_unlocked(' ');
write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
write(x...);
putchar_unlocked('\n');
}
}; // namespace kyopro
/**
* @brief Fast IO(高速入出力)
*/
#line 2 "Library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) std::begin(x), std::end(x)
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::max() / 2;
const long double pi = acosl(-1);
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
return a > b && (a = b, true);
}
/**
* @brief Template
*/
#line 4 "Library/src/data-structure/sparse_table.hpp"
namespace kyopro {
template <class T, auto op> class sparse_table {
std::vector<T> vec;
std::vector<std::vector<T>> table;
std::vector<int> lg;
public:
constexpr sparse_table(int n) : vec(n) {}
constexpr sparse_table(const std::vector<T>& vec) : vec(vec) { build(); }
void set(int p, const T& v) { vec[p] = v; }
void build() {
int sz = vec.size();
int log = 0;
while ((1 << log) <= sz) {
log++;
}
table.assign(log, std::vector<T>(1 << log));
for (int i = 0; i < sz; i++) {
table[0][i] = vec[i];
}
for (int i = 1; i < log; i++) {
for (int j = 0; j + (1 << i) <= (1 << log); j++) {
table[i][j] =
op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
lg.resize(sz + 1);
for (int i = 2; i < (int)lg.size(); i++) {
lg[i] = lg[i >> 1] + 1;
}
}
T fold(int l, int r) const {
int b = lg[r - l];
return op(table[b][l], table[b][r - (1 << b)]);
}
};
}; // namespace kyopro
/**
* @brief Sparse Table
*/
#line 2 "Library/src/internal/CSR.hpp"
#line 7 "Library/src/internal/CSR.hpp"
namespace kyopro {
namespace internal {
template <typename T, typename _size_t> class csr {
_size_t n;
std::vector<T> d;
std::vector<_size_t> ssum;
public:
csr() = default;
csr(_size_t n, const std::vector<std::pair<_size_t, T>>& v)
: n(n), ssum(n + 1), d(v.size()) {
for (int i = 0; i < (int)v.size(); ++i) {
++ssum[v[i].first + 1];
}
for (int i = 0; i < n; ++i) {
ssum[i + 1] += ssum[i];
}
std::vector cnt = ssum;
for (auto e : v) d[cnt[e.first]++] = e.second;
}
struct vector_range {
using iterator = typename std::vector<T>::iterator;
iterator l, r;
iterator begin() const { return l; }
iterator end() const { return r; }
_size_t size() { return std::distance(l, r); }
T& operator[](_size_t i) const { return l[i]; }
};
struct const_vector_range {
using const_iterator = typename std::vector<T>::const_iterator;
const_iterator l, r;
const_iterator begin() const { return l; }
const_iterator end() const { return r; }
_size_t size() { return (_size_t)std::distance(l, r); }
const T& operator[](_size_t i) const { return l[i]; }
};
vector_range operator[](_size_t i) {
return vector_range{d.begin() + ssum[i], d.begin() + ssum[i + 1]};
}
const_vector_range operator[](_size_t i) const {
return const_vector_range{d.begin() + ssum[i], d.begin() + ssum[i + 1]};
}
_size_t size() const { return (_size_t)n; }
};
}; // namespace internal
}; // namespace kyopro
/**
* @brief CSR形式(二次元ベクトルの圧縮)
*/
#line 6 "Library/src/tree/EulerTour.hpp"
namespace kyopro {
class EulerTour {
int n;
std::vector<std::pair<int, int>> es;
std::vector<int> tour;
std::vector<int> in, out, depth;
struct get_min_pair {
using value_t = std::pair<int, int>;
static value_t op(value_t x, value_t y) { return std::min(x, y); }
};
sparse_table<get_min_pair::value_t, get_min_pair::op> rmq;
public:
explicit EulerTour(int n)
: n(n), in(n, -1), out(n, -1), depth(n, -1), rmq(2 * n - 1) {
tour.reserve(2 * n);
es.reserve(2 * n);
}
void add_edge(int u, int v) {
assert(0 <= v && v < n);
assert(0 <= u && u < n);
es.emplace_back(u, v);
es.emplace_back(v, u);
}
int get_depth(int v) const {
assert(0 <= v && v < n);
return depth[v];
}
void build(int r = 0) {
internal::csr g(n, es);
auto dfs = [&](const auto& self, int v, int p) -> void {
in[v] = tour.size();
tour.emplace_back(v);
for (auto nv : g[v]) {
if (nv != p) {
depth[nv] = depth[v] + 1;
self(self, nv, v);
tour.emplace_back(v);
}
}
out[v] = tour.size() - 1;
};
dfs(dfs, r, -1);
for (int i = 0; i < (int)tour.size(); i++) {
rmq.set(i, {depth[tour[i]], tour[i]});
}
rmq.build();
}
std::pair<int, int> idx(int v) const {
assert(0 <= v && v < n);
return {in[v], out[v]};
}
int lca(int v, int u) const {
assert(0 <= v && v < n);
assert(0 <= u && u < n);
if (in[v] > in[u] + 1) {
std::swap(u, v);
}
return rmq.fold(in[v], in[u] + 1).second;
}
int dist(int v, int u) const {
assert(0 <= v && v < n);
assert(0 <= u && u < n);
int p = lca(v, u);
return depth[v] + depth[u] - 2 * depth[p];
}
bool is_in_subtree(int par, int v) const {
assert(0 <= par && par < n);
assert(0 <= v && v < n);
return (in[par] <= in[v] && out[v] <= out[par]);
}
};
}; // namespace kyopro
/**
* @brief Euler Tour
* @docs docs/tree/EulerTour.md
*/
#line 5 "a.cpp"
using namespace std;
using namespace kyopro;
int main() {
int n, r, q;
read(n, r, q);
vector<int> region(n);
vector<vector<int>> vertices(r);
read(region[0]), --region[0];
EulerTour g(n);
for (int i = 1; i < n; ++i) {
int p;
read(p, region[i]), --p, --region[i];
g.add_edge(p, i);
}
g.build(0);
vector<vector<P>> rngs(r);
rep(i, n) rngs[region[i]].emplace_back(g.idx(i));
rep(i, r) sort(all(rngs[i]));
while (q--) {
int r1, r2;
read(r1, r2);
--r1, --r2;
ll ans = 0;
for (auto [l, r] : rngs[r1]) {
int cnt = lower_bound(all(rngs[r2]), pair(r, 0)) -
lower_bound(all(rngs[r2]), pair(l, 0));
ans += cnt;
}
put(ans);
}
}
Compilation message
Library/src/internal/CSR.hpp: In instantiation of 'kyopro::internal::csr<T, _size_t>::csr(_size_t, const std::__debug::vector<std::pair<_Up, _Tp> >&) [with T = int; _size_t = int]':
Library/src/tree/EulerTour.hpp:43:30: required from here
Library/src/internal/CSR.hpp:14:26: warning: 'kyopro::internal::csr<int, int>::ssum' will be initialized after [-Wreorder]
Library/src/internal/CSR.hpp:13:20: warning: 'std::__debug::vector<int> kyopro::internal::csr<int, int>::d' [-Wreorder]
Library/src/internal/CSR.hpp:18:5: warning: when initialized here [-Wreorder]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1 ms |
344 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
1 ms |
344 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
1 ms |
344 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
1 ms |
344 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
2 ms |
344 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
2 ms |
1056 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
2 ms |
856 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
3 ms |
864 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
6 ms |
4184 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
12 ms |
5208 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
19 ms |
5720 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
29 ms |
11840 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
32 ms |
10932 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
36 ms |
11368 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
62 ms |
33364 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
126 ms |
48884 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
133 ms |
45228 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
227 ms |
55888 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
35 ms |
11988 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
48 ms |
29128 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
74 ms |
24252 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
89 ms |
45940 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
147 ms |
66800 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
219 ms |
98832 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
244 ms |
121548 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
263 ms |
98212 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
263 ms |
97416 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
256 ms |
102032 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
296 ms |
99104 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
276 ms |
117652 KB |
Time limit exceeded (wall clock) |
| 16 |
Runtime error |
134 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
137 ms |
131072 KB |
Execution killed with signal 9 |
