#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10, MR = 25010, CASE = 500;
int n, R, Q, sz[N], cnt[MR], re[N], tin[N], tout[N], ti;
vector<int> G[N], ch[N], sml[MR];
vector<vector<int>> ans;
vector<pair<int, int>> lar[MR];
void dfs1(int u, int p){
sz[u] = 1;
tin[u] = ++ti;
for(int v : G[u]){
dfs1(v, u);
sz[u] += sz[v];
}
tout[u] = ti;
}
void dfs2(int u, int p, bool keep){
int bc = -1;
for(int v : G[u]) if(bc == -1 or sz[v] > sz[bc]) bc = v;
for(int v : G[u]) if(v != bc) dfs2(v, u, 0);
if(bc != -1){
dfs2(bc, u, 1);
swap(ch[u], ch[bc]);
}
ch[u].emplace_back(u);
cnt[re[u]]++;
for(int v : G[u]){
if(v == bc) continue;
for(int vv : ch[v]){
cnt[re[vv]]++;
ch[u].emplace_back(vv);
}
}
for(int i = 1; i <= R; i++) ans[re[u]][i] += cnt[i];
if(keep == 0){
for(int v : ch[u]) cnt[re[v]]--;
}
}
void chk(stack<int> st){
cout << "CHKST : ";
while(!st.empty()){
cout << st.top() << " ";
st.pop();
}
cout << "\n";
}
int getans(int r1, int r2){
if(R <= CASE) return ans[r1][r2];
int res = 0;
stack<int> st;
for(int i = 0, j = -1; i < sml[r2].size(); i++){
while(!st.empty() and sml[r2][i] > st.top()) st.pop(); //pop
while(j+1 < lar[r1].size() and lar[r1][j+1].second < sml[r2][i]) j++;
while(j+1 < lar[r1].size() and sml[r2][i] > lar[r1][j+1].first){ //add
st.push(lar[r1][j+1].second);
j++;
}
while(!st.empty() and sml[r2][i] > st.top()) st.pop(); //pop
// chk(st);
res += st.size();
}
return res;
}
int main(void){
cin >> n >> R >> Q;
cin >> re[1];
ans.resize(R+10, vector<int>(R+10));
for(int i = 2; i <= n; i++){
int p; cin >> p >> re[i];
G[p].emplace_back(i);
}
dfs1(1, -1);
if(R <= CASE) dfs2(1, -1, 1);
else {
for(int i = 1; i <= n; i++){
sml[re[i]].emplace_back(tin[i]);
lar[re[i]].emplace_back(tin[i], tout[i]);
}
for(int i = 1; i <= R; i++){
sort(sml[i].begin(), sml[i].end());
sort(lar[i].begin(), lar[i].end());
}
}
while(Q--){
int r1, r2; cin >> r1 >> r2;
cout << getans(r1, r2) << endl;
}
return 0;
}
Compilation message
regions.cpp: In function 'int getans(int, int)':
regions.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0, j = -1; i < sml[r2].size(); i++){
| ~~^~~~~~~~~~~~~~~~
regions.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while(j+1 < lar[r1].size() and lar[r1][j+1].second < sml[r2][i]) j++;
| ~~~~^~~~~~~~~~~~~~~~
regions.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | while(j+1 < lar[r1].size() and sml[r2][i] > lar[r1][j+1].first){ //add
| ~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
10824 KB |
Output is correct |
2 |
Correct |
5 ms |
10824 KB |
Output is correct |
3 |
Correct |
7 ms |
10824 KB |
Output is correct |
4 |
Correct |
10 ms |
10824 KB |
Output is correct |
5 |
Correct |
13 ms |
10824 KB |
Output is correct |
6 |
Correct |
26 ms |
11208 KB |
Output is correct |
7 |
Correct |
36 ms |
11080 KB |
Output is correct |
8 |
Correct |
31 ms |
11080 KB |
Output is correct |
9 |
Correct |
57 ms |
12096 KB |
Output is correct |
10 |
Correct |
98 ms |
12368 KB |
Output is correct |
11 |
Correct |
124 ms |
12164 KB |
Output is correct |
12 |
Correct |
177 ms |
13492 KB |
Output is correct |
13 |
Correct |
218 ms |
13012 KB |
Output is correct |
14 |
Correct |
203 ms |
13056 KB |
Output is correct |
15 |
Correct |
258 ms |
17764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
848 ms |
17400 KB |
Output is correct |
2 |
Correct |
993 ms |
16860 KB |
Output is correct |
3 |
Correct |
1298 ms |
20284 KB |
Output is correct |
4 |
Incorrect |
312 ms |
75840 KB |
Output isn't correct |
5 |
Incorrect |
360 ms |
113140 KB |
Output isn't correct |
6 |
Runtime error |
52 ms |
131076 KB |
Execution killed with signal 9 |
7 |
Runtime error |
55 ms |
131076 KB |
Execution killed with signal 9 |
8 |
Runtime error |
47 ms |
131076 KB |
Execution killed with signal 9 |
9 |
Runtime error |
51 ms |
131076 KB |
Execution killed with signal 9 |
10 |
Runtime error |
51 ms |
131076 KB |
Execution killed with signal 9 |
11 |
Runtime error |
52 ms |
131076 KB |
Execution killed with signal 9 |
12 |
Runtime error |
52 ms |
131076 KB |
Execution killed with signal 9 |
13 |
Runtime error |
55 ms |
131076 KB |
Execution killed with signal 9 |
14 |
Runtime error |
52 ms |
131076 KB |
Execution killed with signal 9 |
15 |
Runtime error |
52 ms |
131076 KB |
Execution killed with signal 9 |
16 |
Runtime error |
53 ms |
131076 KB |
Execution killed with signal 9 |
17 |
Runtime error |
48 ms |
131076 KB |
Execution killed with signal 9 |