#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define sz size
const int mxN = 2e5;
const int mxR = 25*1e3;
int n,r;
vector<int> adj[mxN];
int reg[mxN];
vector<int> all[mxR];
int first[mxN];
int ssize[mxN];
vector<int> ord;
vector<ll> cnts[mxR];
vector<ll> rcnts[mxR];
int tarr[mxN+1];
void dfs(int node, int p){
first[node] = ord.sz();
all[reg[node]].pb(node);
ord.pb(node);
ssize[node] = 1;
for (int next : adj[node]){
if (next != p){
dfs(next,node);
ssize[node] += ssize[next];
}
}
}
int main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
int q;
cin >> n >> r >> q;
int a,b;
cin >> a;
reg[0] = a-1;
for (int i = 1; i < n; i++){
cin >> b >> a;
a -= 1;
b -= 1;
reg[i] = a;
adj[i].pb(b);
adj[b].pb(i);
}
dfs(0,-1);
int gsize = sqrt(n);
for (int i = 0; i < r; i++){
if (all[i].sz() <= gsize){
continue;
}
cnts[i].resize(n);
memset(tarr,0,sizeof(tarr));
for (int j =0; j < all[i].sz(); j++){
tarr[first[all[i][j]]] += 1;
tarr[first[all[i][j]] + ssize[all[i][j]]] -= 1;
}
for (int j = 0; j < n; j++){
if (j > 0) tarr[j] += tarr[j-1];
cnts[i][reg[ord[j]]] += tarr[j];
}
rcnts[i].resize(n);
memset(tarr,0,sizeof(tarr));
for (int j =0; j < all[i].sz(); j++){
tarr[first[all[i][j]]] += 1;
}
for (int j = 1; j < n; j++){
tarr[j] += tarr[j-1];
}
for (int j = 0; j < n; j++){
rcnts[i][reg[ord[j]]] += tarr[j+ssize[ord[j]]-1] - tarr[j];
}
}
/*cout << gsize<< " gsize\n";
for (int i =0; i < r; i++){
cout << all[i].sz() << ":\n";
for (int j = 0; j < all[i].sz(); j++) cout << all[i][j] << " ";
cout << '\n';
if (all[i].sz() <= gsize){
continue;
}
for (int j =0; j < n; j++){
cout << cnts[i][j] << " ";
}
cout << '\n';
for (int j = 0; j < n; j++) cout << rcnts[i][j] << " ";
cout << '\n';
}
*/
int c,idx;
stack<int> p;
ll res;
for (int i =0; i < q; i++){
cin >> a >> b;
a -= 1;
b -= 1;
if (all[a].sz() > gsize){
cout << cnts[a][b] << '\n';
continue;
}
if (all[b].sz() > gsize){
cout << rcnts[b][a] << "\n";
continue;
}
c = 0;
idx = 0;
res = 0;
for (int j = 0; j < all[b].sz(); j++){
while (p.sz() > 0 && p.top() <= j){
p.pop();
c -= 1;
}
while (idx < all[a].sz() && all[a][idx] <= j){
c += 1;
idx++;
p.push(first[all[a][idx]] + ssize[all[a][idx]]);
}
res += c;
}
cout << res << '\n';
while (p.sz() > 0){
p.pop();
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:59:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | if (all[i].sz() <= gsize){
| ~~~~~~~~~~~~^~~~~~~~
regions.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int j =0; j < all[i].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int j =0; j < all[i].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:107:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
107 | if (all[a].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:111:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
111 | if (all[b].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int j = 0; j < all[b].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:123:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | while (idx < all[a].sz() && all[a][idx] <= j){
| ~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
9816 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
9816 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
9816 KB |
Output isn't correct |
| 6 |
Incorrect |
11 ms |
9816 KB |
Output isn't correct |
| 7 |
Incorrect |
13 ms |
9816 KB |
Output isn't correct |
| 8 |
Incorrect |
17 ms |
9816 KB |
Output isn't correct |
| 9 |
Incorrect |
24 ms |
10328 KB |
Output isn't correct |
| 10 |
Incorrect |
43 ms |
10328 KB |
Output isn't correct |
| 11 |
Incorrect |
50 ms |
10504 KB |
Output isn't correct |
| 12 |
Incorrect |
72 ms |
10840 KB |
Output isn't correct |
| 13 |
Incorrect |
89 ms |
10812 KB |
Output isn't correct |
| 14 |
Incorrect |
108 ms |
12760 KB |
Output isn't correct |
| 15 |
Incorrect |
123 ms |
14868 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
487 ms |
41144 KB |
Output isn't correct |
| 2 |
Incorrect |
584 ms |
29900 KB |
Output isn't correct |
| 3 |
Incorrect |
819 ms |
29984 KB |
Output isn't correct |
| 4 |
Incorrect |
184 ms |
11244 KB |
Output isn't correct |
| 5 |
Incorrect |
246 ms |
12980 KB |
Output isn't correct |
| 6 |
Incorrect |
343 ms |
61660 KB |
Output isn't correct |
| 7 |
Incorrect |
545 ms |
68304 KB |
Output isn't correct |
| 8 |
Runtime error |
140 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Incorrect |
958 ms |
17812 KB |
Output isn't correct |
| 10 |
Runtime error |
221 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Incorrect |
1380 ms |
18968 KB |
Output isn't correct |
| 12 |
Incorrect |
585 ms |
24112 KB |
Output isn't correct |
| 13 |
Incorrect |
736 ms |
25136 KB |
Output isn't correct |
| 14 |
Incorrect |
1002 ms |
88008 KB |
Output isn't correct |
| 15 |
Incorrect |
1243 ms |
29364 KB |
Output isn't correct |
| 16 |
Incorrect |
1321 ms |
36668 KB |
Output isn't correct |
| 17 |
Incorrect |
1255 ms |
100924 KB |
Output isn't correct |
