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>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
//mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 2e5+5;
const int mod = 1e9+9;
const int mxlogN = 20;
const int mxK = 26;
const ll inf = 1e18;
const int K=601;
vector<int> adj[mxN], who[mxN];
int p[mxN], h[mxN], in[mxN], out[mxN], _time=0;
vector<int> ls[mxN], rs[mxN];
void dfs(int i)
{
who[h[i]].push_back(i);
in[i]=_time++;
ls[h[i]].push_back(in[i]);
for(int j:adj[i]) dfs(j);
out[i]=_time;
rs[h[i]].push_back(out[i]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, r, q; cin >> n >> r >> q;
cin >> h[1];
for(int i=2; i<=n; i++)
{
cin >> p[i] >> h[i];
adj[p[i]].push_back(i);
}
dfs(1);
vector<int> big;
for(int i=1; i<=r; i++)
{
sort(ls[i].begin(), ls[i].end());
sort(rs[i].begin(), rs[i].end());
sort(who[i].begin(), who[i].end());
if(who[i].size()>K) big.push_back(i);
}
map<pair<int,int>, int> ans;
for(int x:big)
{
for(int y:big)
{
if(x==y) continue;
ll answ=0;
for(int i:who[y])
{
answ-=lower_bound(ls[x].begin(), ls[x].end(), in[i])-ls[x].begin();
answ+=lower_bound(rs[x].begin(), rs[x].end(), in[i])-rs[x].begin();
}
ans[make_pair(x,y)]=answ;
}
}
while(q--)
{
int r, r2; cin >> r >> r2;
if(ans.count(make_pair(r,r2))) cout << ans[make_pair(r,r2)] << "\n";
else
{
ll answ=0;
if(who[r].size()<=K)
{
for(int i:who[r])
{
answ+=lower_bound(ls[r2].begin(),ls[r2].end(),out[i])-ls[r2].begin();
answ-=lower_bound(ls[r2].begin(),ls[r2].end(),in[i])-ls[r2].begin();
}
}
else
{
for(int i:who[r2])
{
answ-=lower_bound(ls[r].begin(), ls[r].end(), in[i])-ls[r].begin();
answ+=lower_bound(rs[r].begin(), rs[r].end(), in[i])-rs[r].begin();
}
}
cout << answ << "\n";
}
cout.flush();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |