/*
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);
{
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++){
if(Color_Index[i].size() < BLOCK_SIZE)
continue;
ans[i].resize(numCol + 1 , 0);
for(auto x : Color_Index[i]){
if(x == numNodes + 1 || x == numNodes + 2) continue;
for(int j = 1 ; j <= numCol ; j++){
if(j == i) continue;
int l = lower_bound(Idx[j].begin() , Idx[j].end() , st[x]) - Idx[j].begin();
int r = upper_bound(Idx[j].begin() , Idx[j].end() , ed[x]) - Idx[j].begin() - 1;
ans[i][j] += max(0 , suf_sum[j][l] - suf_sum[j][r + 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:105:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
105 | if(Color_Index[i].size() < BLOCK_SIZE)
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19664 KB |
Output is correct |
| 2 |
Correct |
12 ms |
19664 KB |
Output is correct |
| 3 |
Correct |
15 ms |
19632 KB |
Output is correct |
| 4 |
Correct |
17 ms |
19588 KB |
Output is correct |
| 5 |
Correct |
16 ms |
19656 KB |
Output is correct |
| 6 |
Correct |
26 ms |
19732 KB |
Output is correct |
| 7 |
Correct |
31 ms |
19720 KB |
Output is correct |
| 8 |
Correct |
40 ms |
19792 KB |
Output is correct |
| 9 |
Correct |
65 ms |
20176 KB |
Output is correct |
| 10 |
Correct |
118 ms |
20232 KB |
Output is correct |
| 11 |
Correct |
129 ms |
20464 KB |
Output is correct |
| 12 |
Correct |
162 ms |
20944 KB |
Output is correct |
| 13 |
Correct |
224 ms |
20908 KB |
Output is correct |
| 14 |
Correct |
311 ms |
21328 KB |
Output is correct |
| 15 |
Correct |
313 ms |
23616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2021 ms |
24300 KB |
Output is correct |
| 2 |
Correct |
2734 ms |
24052 KB |
Output is correct |
| 3 |
Correct |
3520 ms |
26116 KB |
Output is correct |
| 4 |
Correct |
345 ms |
21600 KB |
Output is correct |
| 5 |
Correct |
400 ms |
23112 KB |
Output is correct |
| 6 |
Correct |
5318 ms |
24760 KB |
Output is correct |
| 7 |
Correct |
5678 ms |
26104 KB |
Output is correct |
| 8 |
Execution timed out |
8063 ms |
32576 KB |
Time limit exceeded |
| 9 |
Correct |
2251 ms |
29604 KB |
Output is correct |
| 10 |
Execution timed out |
8036 ms |
39324 KB |
Time limit exceeded |
| 11 |
Correct |
4287 ms |
32424 KB |
Output is correct |
| 12 |
Execution timed out |
8098 ms |
30892 KB |
Time limit exceeded |
| 13 |
Execution timed out |
8070 ms |
31604 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8029 ms |
32176 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8060 ms |
35024 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8055 ms |
40612 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8069 ms |
39628 KB |
Time limit exceeded |
