| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 539183 |
2022-03-18T14:29:10 Z |
fcw |
Regions (IOI09_regions) |
C++17 |
|
4119 ms |
38340 KB |
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;
template<class T> struct segtree_range {
int H, N;
vector<T> ts;
segtree_range() {}
explicit segtree_range(int N_) {
for (H = 0, N = 1; N < N_; ++H, N *= 2) {}
ts.resize(2*N);
}
template<class Q> explicit segtree_range(const vector<Q>& qs) {
const int N_ = int(qs.size());
for (H = 1, N = 1; N < N_; ++H, N *= 2) {}
ts.resize(2*N);
for (int i = 0; i < N_; ++i) at(i) = T(qs[i]);
build();
}
T& at(int a) { return ts[a + N]; }
void build() { for (int a = N; --a; ) merge(a); }
inline void push(int a) { ts[a].push(ts[2 * a], ts[2 * a + 1]); }
inline void merge(int a) { ts[a].merge(ts[2*a], ts[2*a+1]); }
void for_parents_down(int a, int b) {
for (int h = H; h; --h) {
const int l = (a >> h), r = (b >> h);
if (l == r) {
if ((l << h) != a || (r << h) != b) push(l);
} else {
if ((l << h) != a) push(l);
if ((r << h) != b) push(r);
}
}
}
void for_parents_up(int a, int b) {
for (int h = 1; h <= H; ++h) {
const int l = (a >> h), r = (b >> h);
if (l == r) {
if ((l << h) != a || (r << h) != b) merge(l);
} else {
if ((l << h) != a) merge(l);
if ((r << h) != b) merge(r);
}
}
}
template<class F, class... Args> void update(int a, int b, F f, Args&&... args) {
if (a == b) return;
a += N; b += N;
for_parents_down(a, b);
for (int l = a, r = b; l < r; l /= 2, r /= 2) {
if (l & 1) (ts[l++].*f)(args...);
if (r & 1) (ts[--r].*f)(args...);
}
for_parents_up(a, b);
}
T query(int a, int b) {
if (a == b) return T();
a += N; b += N;
for_parents_down(a, b);
T lhs, rhs, t;
for (int l = a, r = b; l < r; l /= 2, r /= 2) {
if (l & 1) { t.merge(lhs, ts[l++]); lhs = t; }
if (r & 1) { t.merge(ts[--r], rhs); rhs = t; }
}
t.merge(lhs, rhs); return t;
}
template<class Op, class E, class F, class... Args>
auto query(int a, int b, Op op, E e, F f, Args&&... args) {
if (a == b) return e();
a += N; b += N;
for_parents_down(a, b);
auto lhs = e(), rhs = e();
for (int l = a, r = b; l < r; l /= 2, r /= 2) {
if (l & 1) lhs = op(lhs, (ts[l++].*f)(args...));
if (r & 1) rhs = op((ts[--r].*f)(args...), rhs);
}
return op(lhs, rhs);
}
// find min i s.t. T::f(args...) returns true in [a, i) from left to right
template<class F, class... Args> int find_right(int a, F f, Args &&... args) {
assert(0 <= a && a <= N);
if ((T().*f)(args...)) return a;
if (a == N) return 1 + N;
a += N;
for (int h = H; h; --h) push(a >> h);
for (; ; a /= 2) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < N; ) {
push(a);
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - N + 1;
}
++a;
if (!(a & (a - 1))) return N + 1;
}
}
// find max i s.t. T::f(args...) returns true in [i, a) from right to left
template<class F, class... Args> int find_left(int a, F f, Args &&... args) {
assert(0 <= a && a <= N);
if ((T().*f)(args...)) return a;
if (a == 0) return -1;
a += N;
for (int h = H; h; --h) push((a - 1) >> h);
for (; ; a /= 2) if ((a & 1) || a == 2) {
if ((ts[a - 1].*f)(args...)) {
for (; a <= N; ) {
push(a - 1);
if (!(ts[(a <<= 1) - 1].*f)(args...)) --a;
}
return a - N - 1;
}
--a;
if (!(a & (a - 1))) return -1;
}
}
};
template<typename T>struct seg_node{
T val;
seg_node(T n = 0): val(n){}
void push(seg_node& l, seg_node& r){
}
void merge(const seg_node& l, const seg_node& r){
val = l.val + r.val;
}
void add(T n){
val += n;
}
T get_sum(){ return val; }
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
//ifstream cin;
//cin.open("promote.in");
//ofstream cout;
//cout.open("promote.out");
int n, r, q;
cin>>n>>r>>q;
vector<vector<int>>g(n);
vector<int>p(n), h(n);
cin>>h[0]; h[0]--;
for(int i=1;i<n;i++){
cin>>p[i]>>h[i];
p[i]--, h[i]--;
g[p[i]].push_back(i);
}
vector<vector<int>>reg(r);
for(int i=0;i<n;i++) reg[h[i]].push_back(i);
int SZ = sqrt(n);
vector<vector<int>>prep(r);
vector<int>heavy;
for(int i=0;i<r;i++){
if((int)reg[i].size() > SZ){
prep[i] = vector<int>(r);
heavy.push_back(i);
}
}
vector<int>tin(n), tout(n), cnt(r);
vector<vector<int>>v(n);
int timer = 0;
auto dfs = [&](auto& self, int u, int p)->void{
tin[u] = timer++;
v[h[u]].push_back(tin[u]);
cnt[h[u]]++;
for(int nxt : g[u]){
if(nxt == p) continue;
self(self, nxt, u);
}
tout[u] = timer;
cnt[h[u]]--;
for(int c : heavy){
if(h[u] == c) continue;
prep[c][h[u]] += cnt[c];
}
};
dfs(dfs, 0, 0);
for(int i=0;i<q;i++){
int a, b;
cin>>a>>b;
a--, b--;
if(!prep[a].empty()){
cout<<prep[a][b]<<endl;
}
else{
int ans = 0;
for(int u : reg[a]){
ans += int(lower_bound(v[b].begin(), v[b].end(), tout[u]) -
lower_bound(v[b].begin(), v[b].end(), tin[u]));
}
cout<<ans<<endl;
}
}
return 0;
}
/*
[ ]Leu o problema certo???
[ ]Ver se precisa de long long
[ ]Viu o limite dos fors (é n? é m?)
[ ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[ ]Testar sample
[ ]Testar casos de borda
[ ]1LL no 1LL << i
[ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| 3 |
Correct |
2 ms |
208 KB |
Output is correct |
| 4 |
Correct |
6 ms |
208 KB |
Output is correct |
| 5 |
Correct |
6 ms |
336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
464 KB |
Output is correct |
| 7 |
Correct |
26 ms |
464 KB |
Output is correct |
| 8 |
Correct |
32 ms |
464 KB |
Output is correct |
| 9 |
Correct |
45 ms |
1232 KB |
Output is correct |
| 10 |
Correct |
48 ms |
1408 KB |
Output is correct |
| 11 |
Correct |
76 ms |
1972 KB |
Output is correct |
| 12 |
Correct |
135 ms |
2844 KB |
Output is correct |
| 13 |
Correct |
182 ms |
2596 KB |
Output is correct |
| 14 |
Correct |
292 ms |
3484 KB |
Output is correct |
| 15 |
Correct |
273 ms |
7792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1557 ms |
9284 KB |
Output is correct |
| 2 |
Correct |
2072 ms |
7964 KB |
Output is correct |
| 3 |
Correct |
2755 ms |
12476 KB |
Output is correct |
| 4 |
Correct |
264 ms |
3912 KB |
Output is correct |
| 5 |
Correct |
342 ms |
6540 KB |
Output is correct |
| 6 |
Correct |
500 ms |
8064 KB |
Output is correct |
| 7 |
Correct |
1128 ms |
10496 KB |
Output is correct |
| 8 |
Correct |
1072 ms |
20916 KB |
Output is correct |
| 9 |
Correct |
2376 ms |
18748 KB |
Output is correct |
| 10 |
Correct |
2823 ms |
37216 KB |
Output is correct |
| 11 |
Correct |
4119 ms |
21188 KB |
Output is correct |
| 12 |
Correct |
1326 ms |
21700 KB |
Output is correct |
| 13 |
Correct |
2037 ms |
22392 KB |
Output is correct |
| 14 |
Correct |
2039 ms |
24240 KB |
Output is correct |
| 15 |
Correct |
3543 ms |
29244 KB |
Output is correct |
| 16 |
Correct |
2835 ms |
38340 KB |
Output is correct |
| 17 |
Correct |
2869 ms |
37696 KB |
Output is correct |
