| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 478215 | Abrar_Al_Samit | Regions (IOI09_regions) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
const int B = 447;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], stwho[MX];
int index[MX], timer=1;
long long prep[B][25001];
void Flat(int v, int p) {
stwho[timer] = v;
st[v] = timer++;
region[H[v]].push_back(st[v]);
for(auto to : g[v]) if(to!=p) {
Flat(to, v);
}
en[v] = timer-1;
}
void DFS(int v, int p, int reg, int cnt) {
if(H[v]==reg) ++cnt;
else prep[index[reg]][H[v]] += cnt;
for(auto u : g[v]) if(u!=p) {
DFS(u, v, reg, cnt);
}
}
int main() {
cin >> N >> R >> Q;
cin >> H[1];
for(int i=2; i<=N; ++i) {
int p; cin >> p >> H[i];
g[p].push_back(i);
}
Flat(1, 1);
int cur = 0;
for(int i=1; i<=R; ++i) if(region[i].size()>B) {
index[i] = cur++;
DFS(1, 1, i, 0);
}
// O(Q(rootNlogN + logR))
while(Q--) {
int r1, r2;
cin >> r1 >> r2;
long long ans = 0;
if(region[r1].size()>B) {
ans = prep[index[r1]][r2];
} else {
for(auto p1 : region[r1]) {
auto it = upper_bound(region[r2].begin(), region[r2].end(), en[stwho[p1]]);
auto it2 = lower_bound(region[r2].begin(), region[r2].end(), p1);
ans += it-it2;
}
}
assert(ans>=0);
cout << ans << endl;
}
return 0;
}