//thatsramen
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)
using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;
//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;
//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set
void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
unsyncIO(); setPrec();
if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}
// #define TEST_CASES
struct SegmentTree {
vector<vector<int>> tre;
int sz;
SegmentTree(vector<int> &a) {
int n = (int) a.size();
sz = 1;
while (sz < n) sz *= 2;
tre.resize(2 * sz);
build(a, 1, 0, sz);
}
vector<int> op(vector<int> &a, vector<int> &b) {
vector<int> res;
int n = a.size(), m = b.size();
int i = 0, j = 0;
while (i < n || j < m) {
if (j == m || (i < n && a[i] < b[j])) {
res.pb(a[i++]);
} else {
res.pb(b[j++]);
}
}
return res;
}
void rcl(int x) {
tre[x] = op(tre[2 * x], tre[2 * x + 1]);
}
void build(vector<int> &a, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < a.size()) {
tre[x] = {a[lx]};
}
return;
}
int m = (lx + rx) / 2;
build(a, 2 * x, lx, m);
build(a, 2 * x + 1, m, rx);
rcl(x);
}
int get(int l, int r, int bb, int x, int lx, int rx) {
if (rx <= l || lx >= r) {
return 0;
}
if (l <= lx && r >= rx) {
int lo = 0, hi = (int) tre[x].size() - 1;
int res = -1;
while (lo <= hi) {
int mi = (lo + hi) / 2;
if (tre[x][mi] <= bb) {
res = mi;
lo = mi + 1;
} else {
hi = mi - 1;
}
}
return res + 1;
}
int m = (lx + rx) / 2;
int s1 = get(l, r, bb, 2 * x, lx, m);
int s2 = get(l, r, bb, 2 * x + 1, m, rx);
return s1 + s2;
}
int get(int l, int r, int bb) {
return get(l, r, bb, 1, 0, sz);
}
};
const int sq = 450;
void solve() {
int n, r, q;
cin >> n >> r >> q;
vector<vector<int>> e(n + 5);
vector<int> region(n + 5), cnt(r + 5, 0);
cin >> region[1];
for (int i = 2; i <= n; i++) {
int p; cin >> p;
e[p].pb(i);
cin >> region[i];
cnt[region[i]]++;
}
vector<int> fun(r + 5, 0);
int pp = 1;
for (int i = 1; i <= r; i++) {
if (cnt[i] > sq) fun[i] = pp++;
}
vector<int> up_cnt(pp + 2, 0);
vector<vector<ll>> pre(pp + 2, vector<ll> (n + 5, 0));
vector<vector<pi>> init(r + 5);
int time = 0;
function<void(int)> dfs = [&](int f) {
int reg = region[f];
for (int i = 1; i < pp; i++)
pre[i][reg] += up_cnt[i];
up_cnt[fun[reg]]++;
pi cur; cur.ft = time++;
for (int to : e[f]) {
dfs(to);
}
cur.sd = time++;
init[reg].pb(cur);
up_cnt[fun[reg]]--;
};
dfs(1);
vector<SegmentTree> sts;
for (int i = 1; i <= r; i++) {
sort(all(init[i]));
vector<int> tru;
for (pi x : init[i]) tru.pb(x.sd);
sts.pb(SegmentTree(tru));
}
for (int i = 0; i < q; i++) {
int r1, r2;
cin >> r1 >> r2;
if (cnt[r1] > sq) {
cout << pre[fun[r1]][r2] << endl;
} else {
int ans = 0;
for (pi x : init[r1]) {
pi val = {x.ft, -IINF};
int j = lower_bound(all(init[r2]), val) - init[r2].begin();
ans += sts[r2 - 1].get(j, (int) init[r2].size(), x.sd);
}
cout << ans << endl;
}
}
}
int main() {
setIO();
int tt = 1;
#ifdef TEST_CASES
cin >> tt;
#endif
while (tt--)
solve();
return 0;
}
Compilation message
regions.cpp: In member function 'void SegmentTree::build(std::vector<int>&, int, int, int)':
regions.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | if (lx < a.size()) {
| ~~~^~~~~~~~~~
regions.cpp: In function 'void setIn(std::string)':
regions.cpp:44:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | void setIn(string s) {freopen(s.c_str(), "r", stdin);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void setOut(std::string)':
regions.cpp:45:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | void setOut(string s) {freopen(s.c_str(), "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
312 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
2 ms |
208 KB |
Output is correct |
| 4 |
Correct |
5 ms |
336 KB |
Output is correct |
| 5 |
Correct |
7 ms |
336 KB |
Output is correct |
| 6 |
Correct |
13 ms |
464 KB |
Output is correct |
| 7 |
Correct |
26 ms |
592 KB |
Output is correct |
| 8 |
Correct |
39 ms |
720 KB |
Output is correct |
| 9 |
Correct |
67 ms |
1872 KB |
Output is correct |
| 10 |
Correct |
72 ms |
2640 KB |
Output is correct |
| 11 |
Correct |
110 ms |
3796 KB |
Output is correct |
| 12 |
Correct |
183 ms |
5488 KB |
Output is correct |
| 13 |
Correct |
186 ms |
6008 KB |
Output is correct |
| 14 |
Correct |
508 ms |
8012 KB |
Output is correct |
| 15 |
Correct |
638 ms |
13568 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3854 ms |
29564 KB |
Output is correct |
| 2 |
Correct |
4307 ms |
28004 KB |
Output is correct |
| 3 |
Correct |
5743 ms |
32000 KB |
Output is correct |
| 4 |
Correct |
330 ms |
7836 KB |
Output is correct |
| 5 |
Correct |
433 ms |
11212 KB |
Output is correct |
| 6 |
Correct |
530 ms |
37140 KB |
Output is correct |
| 7 |
Correct |
2497 ms |
24308 KB |
Output is correct |
| 8 |
Correct |
1309 ms |
107676 KB |
Output is correct |
| 9 |
Correct |
3489 ms |
40032 KB |
Output is correct |
| 10 |
Correct |
6802 ms |
117740 KB |
Output is correct |
| 11 |
Execution timed out |
8009 ms |
46848 KB |
Time limit exceeded |
| 12 |
Correct |
2369 ms |
48836 KB |
Output is correct |
| 13 |
Correct |
3228 ms |
49528 KB |
Output is correct |
| 14 |
Correct |
3080 ms |
84908 KB |
Output is correct |
| 15 |
Correct |
6037 ms |
58232 KB |
Output is correct |
| 16 |
Correct |
6381 ms |
64260 KB |
Output is correct |
| 17 |
Correct |
5489 ms |
99032 KB |
Output is correct |
