| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 311356 | caoash | Regions (IOI09_regions) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
const int MX = 200005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;
namespace output {
void pr(int x) {
cout << x;
}
void pr(long x) {
cout << x;
}
void pr(ll x) {
cout << x;
}
void pr(unsigned x) {
cout << x;
}
void pr(unsigned long x) {
cout << x;
}
void pr(unsigned long long x) {
cout << x;
}
void pr(float x) {
cout << x;
}
void pr(double x) {
cout << x;
}
void pr(long double x) {
cout << x;
}
void pr(char x) {
cout << x;
}
void pr(const char * x) {
cout << x;
}
void pr(const string & x) {
cout << x;
}
void pr(bool x) {
pr(x ? "true" : "false");
}
template < class T1, class T2 > void pr(const pair < T1, T2 > & x);
template < class T > void pr(const T & x);
template < class T, class...Ts > void pr(const T & t,
const Ts & ...ts) {
pr(t);
pr(ts...);
}
template < class T1, class T2 > void pr(const pair < T1, T2 > & x) {
pr("{", x.f, ", ", x.s, "}");
}
template < class T > void pr(const T & x) {
pr("{"); // const iterator needed for vector<bool>
bool fst = 1;
for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0;
pr("}");
}
void ps() {
pr("\n");
} // print w/ spaces
template < class T, class...Ts > void ps(const T & t,
const Ts & ...ts) {
pr(t);
if (sizeof...(ts)) pr(" ");
ps(ts...);
}
void pc() {
cout << "]" << endl;
} // debug w/ commas
template < class T, class...Ts > void pc(const T & t,
const Ts & ...ts) {
pr(t);
if (sizeof...(ts)) pr(", ");
pc(ts...);
}
#define dbg(x...) pr("[", #x, "] = ["), pc(x);
}
#ifdef LOCAL
using namespace output;
#endif
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
vi adj[MX];
int nr[MX];
int p[MX];
gp_hash_table<pi, int> ans;
map<int, int> vals[MX];
void mrg(map<int, int> &v1, map<int, int> &v2) {
if (sz(v1) < sz(v2)) swap(v1, v2);
for (auto x : v2) v1[x.f] += x.s;
v2.clear();
}
void dfs(int v, int p) {
vals[v][nr[v]]++;
for (int to : adj[v]) {
if (to != p) {
dfs(to, v);
mrg(vals[v], vals[to]);
}
}
for (auto x : vals[v]) ans[mp(nr[v], x.f)] += x.s;
// dbg(v, vals[v]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, r, q; cin >> n >> r >> q;
cin >> nr[0];
for (int i = 1; i < n; i++) cin >> p[i] >> nr[i];
for (int i = 1; i < n; i++) {
// dbg(i, p[i]);
// dbg(p[i] - 1, i);
adj[p[i] - 1].pb(i);
}
dfs(0, -1);
for (int i = 0; i < q; i++) {
int qu, qv; cin >> qu >> qv;
cout << ans[mp(qu, qv)] << endl;
}
}