#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif
#define lsb(x) (x&(-x))
#define g(i,x) get<i>(x)
const int MAXN = 2e5 + 5;
const int MAXR = 3e4 + 5;
int N, R, Q, regions[MAXN], tour[MAXN], tme[MAXN][2];
vector<int> adj[MAXN];
vector<pair<int, int>> regionRanges[MAXR];
vector<int> regionIds[MAXR];
int regionDepth[MAXR];
// Euler tour
int timer = 0;
void dfs(int n, int p = 1){
tour[timer] = n;
tme[n][0] = timer++;
regionDepth[regions[n]]++;
regionRanges[regions[n]].push_back({tme[n][0], regionDepth[regions[n]]});
regionIds[regions[n]].push_back(tme[n][0]);
for(int e : adj[n]){
if(e == p) continue;
dfs(e, n);
}
regionDepth[regions[n]]--;
tme[n][1] = timer;
regionRanges[regions[n]].push_back({tme[n][1], regionDepth[regions[n]]});
}
// Precomputation
int rtp[MAXR], precomp[500][MAXR][2];
void precompFirst(int r, int p){
// if no nodes have region r, immediately return
if(regionRanges[r].empty()) return;
int idx = 0;
for(int i = regionRanges[r][0].first; i < N; i++){
while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
idx++;
}
precomp[p][regions[tour[i]]][0] += regionRanges[r][idx].second;
}
}
void precompSecond(int r, int p){
for(int i = 1; i <= R; i++){
int idx = 0;
for(int p2 : regionIds[r]){
while(idx < regionRanges[i].size() - 1 && regionRanges[i][idx+1].first <= p2){
idx++;
}
precomp[p][i][1] += regionRanges[i][idx].second;
}
}
}
// Non-precomputed query
int query(int r1, int r2){
int res = 0, idx = 0;
for(int p2 : regionIds[r2]){
while(idx != regionRanges[r1].size() - 1 && regionRanges[r1][idx+1].first <= p2){
idx++;
}
res += regionRanges[r1][idx].second;
}
return res;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> R >> Q >> regions[1];
for(int i = 2; i <= N; i++){
int sk, hk;
cin >> sk >> hk;
adj[sk].push_back(i);
adj[i].push_back(sk);
regions[i] = hk;
}
dfs(1);
// Precompute largest
int idx = 0;
for(int i = 1; i <= R; i++){
if(regionIds[i].size() >= N/sqrt(N)){
rtp[i] = idx;
precompFirst(i, idx);
precompSecond(i, idx);
idx++;
}
}
for(int z = 0; z < Q; z++){
int r1, r2;
cin >> r1 >> r2;
if(regionIds[r1].size() >= N/sqrt(N)){
D("Precomp r1\n");
cout << precomp[rtp[r1]][r2][0] << "\n";
cout.flush();
continue;
}
if(regionIds[r2].size() >= N/sqrt(N)){
D("Precomp r2\n");
cout << precomp[rtp[r2]][r1][1] << "\n";
cout.flush();
continue;
}
cout << query(r1, r2) << "\n";
cout.flush();
}
}
Compilation message
regions.cpp: In function 'void precompFirst(int, int)':
regions.cpp:54: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]
54 | while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void precompSecond(int, int)':
regions.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while(idx < regionRanges[i].size() - 1 && regionRanges[i][idx+1].first <= p2){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int query(int, int)':
regions.cpp:79: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]
79 | while(idx != regionRanges[r1].size() - 1 && regionRanges[r1][idx+1].first <= p2){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
12860 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
13 ms |
12788 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
11 ms |
12880 KB |
Execution killed with signal 11 |
| 4 |
Incorrect |
5 ms |
6352 KB |
Output isn't correct |
| 5 |
Incorrect |
10 ms |
6480 KB |
Output isn't correct |
| 6 |
Runtime error |
11 ms |
13064 KB |
Execution killed with signal 11 |
| 7 |
Incorrect |
28 ms |
6480 KB |
Output isn't correct |
| 8 |
Incorrect |
31 ms |
6608 KB |
Output isn't correct |
| 9 |
Incorrect |
44 ms |
7248 KB |
Output isn't correct |
| 10 |
Incorrect |
67 ms |
7248 KB |
Output isn't correct |
| 11 |
Incorrect |
65 ms |
7676 KB |
Output isn't correct |
| 12 |
Incorrect |
103 ms |
8420 KB |
Output isn't correct |
| 13 |
Incorrect |
132 ms |
8528 KB |
Output isn't correct |
| 14 |
Incorrect |
154 ms |
9088 KB |
Output isn't correct |
| 15 |
Incorrect |
189 ms |
13424 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
527 ms |
13576 KB |
Output isn't correct |
| 2 |
Incorrect |
843 ms |
12892 KB |
Output isn't correct |
| 3 |
Incorrect |
1232 ms |
16376 KB |
Output isn't correct |
| 4 |
Runtime error |
27 ms |
18192 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
31 ms |
23428 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
42 ms |
22016 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
46 ms |
25272 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
66 ms |
41288 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
86 ms |
41924 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
113 ms |
56968 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
104 ms |
46316 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
108 ms |
42692 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
102 ms |
45776 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
114 ms |
45580 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
387 ms |
57912 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
133 ms |
79632 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
116 ms |
75700 KB |
Execution killed with signal 11 |
