/*
Cred : SunnyYeahBoi
Currently Coding at school :>
Problem :
*/
#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define double long double
//#define endl '\n'
const int MAXN = 200005;
const int MAXR = 25005;
const int INF = INT_MAX;
const int MOD = 1e9 + 7;
int pow_mod(int a , int b){
a %= MOD;
if(b == 0) return 1;
if(b == 1) return a;
int tmp = pow_mod(a , b / 2);
if(b % 2 == 0)
return (tmp * tmp) % MOD;
else return ((tmp * tmp) % MOD * a) % MOD;
}
int numNodes , numCol , numQueries;
vector<int> Color_Index[MAXR];
vector<int> Idx[MAXN];
vector<int> g[MAXN];
vector<int> ans[MAXN];
int st[MAXN] , ed[MAXN] , timeDFS = 0;
vector<int> suf_sum[MAXN];
bool cmp(int a , int b){
return st[a] < st[b];
}
bool cmp2(int a , int b){
return a < st[b];
}
bool cmp3(int a , int b){
return st[a] < b;
}
void DFS(int u , int par = -1){
timeDFS++;
st[u] = timeDFS;
for(auto v : g[u]){
if(v == par) continue;
DFS(v , u);
}
ed[u] = timeDFS;
}
int BLOCK_SIZE;
void solve(){
cin >> numNodes >> numCol >> numQueries;
BLOCK_SIZE = sqrt(numNodes) + 5;
{
int x;
cin >> x;
Color_Index[x].push_back(1);
}
for(int i = 2 ; i <= numNodes ; i++){
int col , par;
cin >> par >> col;
g[par].push_back(i);
g[i].push_back(par);
Color_Index[col].push_back(i);
}
// Read the Input
DFS(1);
st[numNodes + 1] = INF;
st[numNodes + 2] = -INF;
for(int i = 1 ; i <= numCol ; i++){
Color_Index[i].push_back(numNodes + 1);
Color_Index[i].push_back(numNodes + 2);
Idx[i] = Color_Index[i];
for(int j = 0 ; j < Idx[i].size() ; j++) Idx[i][j] = st[Idx[i][j]];
sort(Idx[i].begin() , Idx[i].end());
suf_sum[i].resize(Color_Index[i].size());
suf_sum[i][suf_sum[i].size() - 1] = 0;
for(int j = (int)suf_sum[i].size() - 2 ; j >= 1 ; j--)
suf_sum[i][j] = suf_sum[i][j + 1] + 1;
suf_sum[i][0] = suf_sum[i][1];
}
for(int i = 1 ; i <= numCol ; i++){
vector<int> pref_sum(numNodes + 1 , 0);
for(auto x : Idx[i])
if(x > 0 && x <= numNodes)pref_sum[x] += 1;
for(int j = 1 ; j <= numNodes ; j++)
pref_sum[j] = pref_sum[j - 1] + pref_sum[j];
for(int j = 1 ; j <= numCol ; j++){
if(Idx[j].size() < BLOCK_SIZE) continue;
if(j == i) continue;
if(ans[j].size() == 0) ans[j].resize(numCol + 5 , 0);
for(auto x : Color_Index[j]){
if(x == numNodes + 1 || x == numNodes + 2) continue;
ans[j][i] += pref_sum[ed[x]] - pref_sum[st[x] - 1];
}
}
}
// for(int i = 1 ; i <= numNodes ; i++){
// if(Color_Index[i].size() == 0) continue;
// cout << "Color : " << i << endl;
// for(auto x : Idx[i])
// cout << x << " ";
// cout << endl;
// }
while(numQueries--){
int r1 , r2;
cin >> r1 >> r2;
if(ans[r1].size() > 0){
cout << ans[r1][r2] << endl;
}else{
int res = 0;
for(auto x : Color_Index[r1]){
if(x == numNodes + 1 || x == numNodes + 2) continue;
int l = lower_bound(Idx[r2].begin() , Idx[r2].end() , st[x]) - Idx[r2].begin();
int r = upper_bound(Idx[r2].begin() , Idx[r2].end() , ed[x]) - Idx[r2].begin() - 1;
//cout << r1 << " " << r2 << " " << st[x] << " " << ed[x] << " " << l << " " << r << " " << suf_sum[r2][l] - suf_sum[r2][r + 1] << endl;
res += max(0 , suf_sum[r2][l] - suf_sum[r2][r + 1]);
}
cout << res << endl;
}
}
}
int32_t main(){
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen(".INP" , "r" , stdin);
// freopen(".OUT" , "w" , stdout);
solve();
return 0;
}
Compilation message
regions.cpp: In function 'void solve()':
regions.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int j = 0 ; j < Idx[i].size() ; j++) Idx[i][j] = st[Idx[i][j]];
| ~~^~~~~~~~~~~~~~~
regions.cpp:112:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
112 | if(Idx[j].size() < BLOCK_SIZE) continue;
| ~~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19744 KB |
Output is correct |
| 2 |
Correct |
12 ms |
19692 KB |
Output is correct |
| 3 |
Correct |
13 ms |
19664 KB |
Output is correct |
| 4 |
Correct |
17 ms |
19664 KB |
Output is correct |
| 5 |
Correct |
19 ms |
19704 KB |
Output is correct |
| 6 |
Correct |
29 ms |
19664 KB |
Output is correct |
| 7 |
Correct |
40 ms |
19664 KB |
Output is correct |
| 8 |
Correct |
46 ms |
19792 KB |
Output is correct |
| 9 |
Correct |
63 ms |
20220 KB |
Output is correct |
| 10 |
Correct |
125 ms |
20228 KB |
Output is correct |
| 11 |
Correct |
163 ms |
20560 KB |
Output is correct |
| 12 |
Correct |
205 ms |
21048 KB |
Output is correct |
| 13 |
Correct |
213 ms |
21116 KB |
Output is correct |
| 14 |
Correct |
291 ms |
21444 KB |
Output is correct |
| 15 |
Correct |
319 ms |
23844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1782 ms |
24584 KB |
Output is correct |
| 2 |
Correct |
2029 ms |
24360 KB |
Output is correct |
| 3 |
Correct |
3021 ms |
26340 KB |
Output is correct |
| 4 |
Correct |
618 ms |
21704 KB |
Output is correct |
| 5 |
Correct |
891 ms |
23356 KB |
Output is correct |
| 6 |
Correct |
2356 ms |
24980 KB |
Output is correct |
| 7 |
Correct |
3957 ms |
26460 KB |
Output is correct |
| 8 |
Correct |
5987 ms |
33136 KB |
Output is correct |
| 9 |
Execution timed out |
8036 ms |
30256 KB |
Time limit exceeded |
| 10 |
Execution timed out |
8032 ms |
45128 KB |
Time limit exceeded |
| 11 |
Execution timed out |
8061 ms |
33208 KB |
Time limit exceeded |
| 12 |
Execution timed out |
8029 ms |
31712 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8026 ms |
32432 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8042 ms |
34476 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8035 ms |
35952 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8023 ms |
41488 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8029 ms |
41840 KB |
Time limit exceeded |
