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>
#define pb push_back
#define ll long long
#define mp make_pair
#define pb push_back
using namespace std;
const int nax = 501;
const int NAX = 500*500 + 1;
int N,R,Q;
vector<int>S(NAX);
vector<int>H(NAX);
vector<int>adj[NAX];
vector<int>rs[25001];
int lend[NAX];
int ans[400][25005];
int tour[NAX];
int mapa[NAX], p[NAX];
int main() {
scanf("%d%d%d", &N, &R, &Q);
scanf("%d", &H[1]);
for (int i = 2; i<=N; i++){
scanf("%d%d", &S[i], &H[i]);
adj[S[i]].pb(i);
}
int timer = 0;
function<void(int)>Dfs = [&](int u){
lend[u]=timer++;
mapa[timer-1] = u;
for (int& x : adj[u])Dfs(x);
rs[H[u]].pb(lend[u]);
tour[u]=timer-1;
};
Dfs(1);
memset(ans, 0, sizeof(ans));
function<void(int, int, int)>Dfs2 = [&](int u, int r2, int brojac){
if (H[u] == r2)++brojac;
ans[p[r2]][H[u]]+=brojac;
for (int& x : adj[u]){
Dfs2(x, r2, brojac);
}
};
int c = 0;
for(int i = 1; i<=R; i++){
sort(rs[i].begin(), rs[i].end());
if (rs[i].size() <= 500)continue;
p[i]=++c;
Dfs2(1,i,0);
}
while(Q--){
int a,b;
cin >> a >> b;
if (rs[a].size() > 500){
printf("%d\n", ans[p[a]][b]);
fflush(stdout);
}
else{
int tot = 0;
for(int i = 0; i < (int)rs[a].size(); i++){
int l = rs[a][i];
int r = tour[mapa[l]];
int it1 = lower_bound(rs[b].begin(), rs[b].end(), l) - rs[b].begin();
int it2 = lower_bound(rs[b].begin(), rs[b].end(), r+1) - rs[b].begin();
tot+=(it2 - it1);
}
printf("%d\n", tot);
fflush(stdout);
}
}
return 0;
}
Compilation message (stderr)
regions.cpp: In function 'int main()':
regions.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | scanf("%d%d%d", &N, &R, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d", &H[1]);
| ~~~~~^~~~~~~~~~~~~
regions.cpp:22:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d%d", &S[i], &H[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |