#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 <r; i++){
cout << i << ": ";
for (int j : all[i]){
cout << first[j] << "-" << ssize[j] << " ";
}
cout << '\n';
}*/
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;
// cout << a << "," << b << ": ";
for (int j = 0; j < all[b].sz(); j++){
// cout << p.sz() << " " << idx << " " << all[a].sz() << '\n';
while (p.sz() > 0 && p.top() <= first[all[b][j]]){
p.pop();
// cout << "Rm\n";
c -= 1;
}
// cout << ";\n";
while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
c += 1;
// cout << all[a][idx] << '\n';
p.push(first[all[a][idx]] + ssize[all[a][idx]]);
idx++;
while (p.sz() > 0 && p.top() <= first[all[b][j]]){
p.pop();
c -= 1;
}
}
// cout << p.sz() << "l\n";
// cout << c << ' ' << p.top() << '\n';
// cout << c << '\n';
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:114:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if (all[a].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:118:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
118 | if (all[b].sz() > gsize){
| ~~~~~~~~~~~~^~~~~~~
regions.cpp:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int j = 0; j < all[b].sz(); j++){
| ~~^~~~~~~~~~~~~
regions.cpp:134:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | while (idx < all[a].sz() && first[all[a][idx]] <= first[all[b][j]]){
| ~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9824 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9816 KB |
Output is correct |
| 5 |
Correct |
7 ms |
9816 KB |
Output is correct |
| 6 |
Correct |
13 ms |
9816 KB |
Output is correct |
| 7 |
Correct |
20 ms |
9816 KB |
Output is correct |
| 8 |
Correct |
18 ms |
9816 KB |
Output is correct |
| 9 |
Correct |
26 ms |
10328 KB |
Output is correct |
| 10 |
Correct |
51 ms |
10332 KB |
Output is correct |
| 11 |
Correct |
80 ms |
10504 KB |
Output is correct |
| 12 |
Correct |
87 ms |
10948 KB |
Output is correct |
| 13 |
Correct |
118 ms |
10816 KB |
Output is correct |
| 14 |
Correct |
148 ms |
12776 KB |
Output is correct |
| 15 |
Correct |
189 ms |
14864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
705 ms |
41132 KB |
Output is correct |
| 2 |
Correct |
842 ms |
29888 KB |
Output is correct |
| 3 |
Correct |
1416 ms |
29980 KB |
Output is correct |
| 4 |
Correct |
185 ms |
11072 KB |
Output is correct |
| 5 |
Correct |
283 ms |
13000 KB |
Output is correct |
| 6 |
Correct |
372 ms |
61652 KB |
Output is correct |
| 7 |
Correct |
608 ms |
68304 KB |
Output is correct |
| 8 |
Runtime error |
132 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Correct |
1401 ms |
17800 KB |
Output is correct |
| 10 |
Runtime error |
183 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Correct |
2442 ms |
18916 KB |
Output is correct |
| 12 |
Correct |
865 ms |
24112 KB |
Output is correct |
| 13 |
Correct |
1122 ms |
25136 KB |
Output is correct |
| 14 |
Correct |
1276 ms |
88008 KB |
Output is correct |
| 15 |
Correct |
1924 ms |
29368 KB |
Output is correct |
| 16 |
Correct |
1935 ms |
36660 KB |
Output is correct |
| 17 |
Correct |
1861 ms |
100924 KB |
Output is correct |
