#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
const ll B=1400;
vector<ll>adj[220005];
bool vis[220005];
ll siz[220005],dep[220005];
ll rem[220005];
bool used[220005];
vector<ll>compo[220005];
int fa[220005];
ll inside[220005];
ll tin[220005],tout[220005];
ll disc[250005];
vector<ll>reg[25005];
vector<ll>blk[145];
ll timer=1;
map<pair<ll,ll>,bool>hv;
map<pair<ll,ll>,ll>ans;
ll ass;
void dfs(ll s){
vis[s]=1;
siz[s]=1;
tin[s]=timer++;
for(auto& u: adj[s]){
if(!vis[u]){
dep[u]=dep[s]+1;
fa[u]=s;
dfs(u);
siz[s]+=siz[u];
}
}
tout[s]=timer;
}
void create(ll s){
if(used[s])return;
used[s]=1;
inside[s]=ass;
for(auto& u: adj[s]){
if(!used[u]){
create(u);
}
}
}
struct node{
ll id,dep;
bool operator<(const node& n)const{
return dep<n.dep;
}
node(ll _id, ll _dep){
id=_id,dep=_dep;
}
};
ll cnt[145][25005];
ll tot[145][25005];
ll store[145];
ll home[200005];
ll anc(ll u, ll v){
return ((tin[u]<=tin[v])&&(tout[u]>=tout[v])&&(u!=v));
}
vector<node>revdep;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n,r,q;
cin>>n>>r>>q;
for(int i=1;i<=n;i++){
if(i==1){
cin>>home[i];
reg[home[i]].pb(i);
}
else{
ll con;
cin>>con;
adj[con].push_back(i);
cin>>home[i];
reg[home[i]].pb(i);
}
}
ass=n+1;
dfs(1);
for(int i=1;i<=n;i++){
inside[i]=i;
revdep.pb(node(i,dep[i]));
}
sort(revdep.rbegin(),revdep.rend());
for(int i=0;i<revdep.size();i++){
ll s=revdep[i].id;
rem[s]=1;
for(auto& u: adj[s]){
rem[s]+=rem[u];
}
ll sz=0;
vector<ll>cur;
for(auto& u: adj[s]){
sz+=rem[u];
cur.pb(u);
if(sz>=B){
rem[s]-=sz;
sz=0;
for(auto& k: cur){
create(k);
}
fa[ass]=s;
ass++;
cur.clear();
}
}
if(s==1){
for(auto& k: cur){
create(k);
}
fa[ass]=s;
ass++;
cur.clear();
}
}
vector<ll>lis;
for(int i=1;i<=n;i++){
lis.pb(inside[i]);
}
for(int i=1;i<=n;i++){
compo[inside[i]].pb(i);
}
sort(lis.begin(),lis.end());
lis.erase(unique(lis.begin(),lis.end()),lis.end());
for(int i=0;i<lis.size();i++){
disc[lis[i]]=i+1;
}
for(int i: lis){
for(auto& u: compo[i]){
cnt[disc[i]][home[u]]++;
}
}
for(int i=1;i<=n;i++){
adj[i].clear();
}
for(auto& u: lis){
compo[u].clear();
}
fa[1]=0;
for(auto& u: lis){
int popo=fa[u];
// cout<<popo<<" ";
while(popo!=1&&popo!=0){
// cout<<popo<<" ";
tot[disc[u]][home[popo]]++;
popo=fa[popo];
}
if(popo==0)continue;
tot[disc[u]][home[popo]]++;
}
while(q--){
ll a,b;
cin>>a>>b;
if(hv[{a,b}]){cout<<ans[{a,b}]<<'\n';continue;};
ll an=0;
for(auto& u: reg[b]){
blk[disc[inside[u]]].pb(u);
}
for(auto& u: reg[a]){
for(auto& k: blk[disc[inside[u]]]){
if(anc(u,k)){
an++;
}
}
}
for(auto& u: reg[b]){
blk[disc[inside[u]]].clear();
}
ll first=0;
for(auto& u: lis){
first+=tot[disc[u]][a]*cnt[disc[u]][b];
}
hv[{a,b}]=1,ans[{a,b}]=first+an;
cout<<first+an<<endl;
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i=0;i<revdep.size();i++){
| ~^~~~~~~~~~~~~~
regions.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i=0;i<lis.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
23128 KB |
Output is correct |
| 2 |
Execution timed out |
4 ms |
23128 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
4 ms |
23196 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
4 ms |
23204 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
4 ms |
23228 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
5 ms |
23572 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
5 ms |
23300 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
5 ms |
23596 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
9 ms |
24180 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
8 ms |
23824 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
8 ms |
23896 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
12 ms |
25276 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
19 ms |
26604 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
17 ms |
29012 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
26 ms |
33368 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
35 ms |
36736 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
49 ms |
35228 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
39 ms |
43212 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
90 ms |
31928 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
36 ms |
32096 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
24 ms |
30408 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
32 ms |
35520 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
48 ms |
46888 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
112 ms |
49940 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
128 ms |
61488 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
121 ms |
53484 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
164 ms |
55404 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
318 ms |
58760 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
170 ms |
59716 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
160 ms |
65384 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
170 ms |
74460 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
120 ms |
72176 KB |
Time limit exceeded (wall clock) |
