#include <bits/stdc++.h>
using namespace std;
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;
vvi reg, graph;
vi regi;
vi st, en;
int timer = 0;
void dfs(int x, int par, vll &vec)
{
vec[regi[x]]++;
for (auto e : graph[x])
{
if (e != par)
{
dfs(e, x, vec);
}
}
}
void euler(int x, int par)
{
st[x] = ++timer;
for (auto e : graph[x])
{
if (e != par)
{
euler(e, x);
}
}
en[x] = timer;
}
int main()
{
int n, r, q;
scd(n);
scd(r);
scd(q);
int x = 500;
reg = vvi(r + 1);
regi = vi(n + 1);
int h;
scd(h);
reg[h].pb(1);
regi[1] = h;
graph = vvi(n + 1);
vi par(n + 1);
forr(i, 2, n + 1)
{
int p, h;
scd(p);
scd(h);
reg[h].pb(i);
graph[i].pb(p);
graph[p].pb(i);
regi[i] = h;
par[i] = p;
}
vector<vll> prec(r + 1);
forr(i, 1, r + 1)
{
if (reg[i].size() > x)
{
vll out(n+1);
for(auto e : reg[i])
dfs(e, par[e], out);
prec[i] = out;
}
}
st = en = vi(n + 1);
vvi pos(r + 1);
euler(1, 0);
forr(i, 1, r + 1)
{
for (auto e : reg[i])
{
pos[i].pb(st[e]);
}
sort(all(pos[i]));
// printf("%d\n", i);
// for(auto e : pos[i]) printf("%d ", e);
// printf("\n");
}
frange(_, q)
{
int a, b;
scd(a);
scd(b);
if (reg[a].size() > x)
{
printf("%lld\n", prec[a][b]);
fflush(stdout);
}
else
{
lli tot = 0;
for (auto e : reg[a])
{
tot += upper_bound(all(pos[b]), en[e]) - lower_bound(all(pos[b]), st[e]);
// printf("%d %d %lld\n", st[e], en[e], tot);
}
printf("%lld\n", tot);
fflush(stdout);
}
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:89:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | if (reg[i].size() > x)
| ~~~~~~~~~~~~~~^~~
regions.cpp:117:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
117 | if (reg[a].size() > x)
| ~~~~~~~~~~~~~~^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:60:5: note: in expansion of macro 'scd'
60 | scd(n);
| ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:61:5: note: in expansion of macro 'scd'
61 | scd(r);
| ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:62:5: note: in expansion of macro 'scd'
62 | scd(q);
| ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:67:5: note: in expansion of macro 'scd'
67 | scd(h);
| ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:76:9: note: in expansion of macro 'scd'
76 | scd(p);
| ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:77:9: note: in expansion of macro 'scd'
77 | scd(h);
| ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:115:9: note: in expansion of macro 'scd'
115 | scd(a);
| ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define scd(t) scanf("%d", &t)
| ~~~~~^~~~~~~~~~
regions.cpp:116:9: note: in expansion of macro 'scd'
116 | scd(b);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
272 KB |
Output is correct |
| 3 |
Correct |
2 ms |
208 KB |
Output is correct |
| 4 |
Correct |
4 ms |
208 KB |
Output is correct |
| 5 |
Correct |
10 ms |
336 KB |
Output is correct |
| 6 |
Correct |
12 ms |
336 KB |
Output is correct |
| 7 |
Correct |
15 ms |
336 KB |
Output is correct |
| 8 |
Correct |
23 ms |
464 KB |
Output is correct |
| 9 |
Correct |
36 ms |
848 KB |
Output is correct |
| 10 |
Correct |
61 ms |
1104 KB |
Output is correct |
| 11 |
Correct |
113 ms |
1568 KB |
Output is correct |
| 12 |
Correct |
87 ms |
2128 KB |
Output is correct |
| 13 |
Correct |
164 ms |
2256 KB |
Output is correct |
| 14 |
Correct |
215 ms |
2768 KB |
Output is correct |
| 15 |
Correct |
234 ms |
5524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5278 ms |
14104 KB |
Output is correct |
| 2 |
Correct |
2519 ms |
15044 KB |
Output is correct |
| 3 |
Execution timed out |
8039 ms |
16220 KB |
Time limit exceeded |
| 4 |
Correct |
241 ms |
3280 KB |
Output is correct |
| 5 |
Correct |
336 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
1231 ms |
5440 KB |
Output is correct |
| 7 |
Correct |
1526 ms |
7256 KB |
Output is correct |
| 8 |
Correct |
952 ms |
12796 KB |
Output is correct |
| 9 |
Correct |
2119 ms |
15256 KB |
Output is correct |
| 10 |
Correct |
3425 ms |
21148 KB |
Output is correct |
| 11 |
Correct |
3288 ms |
19696 KB |
Output is correct |
| 12 |
Correct |
3232 ms |
20196 KB |
Output is correct |
| 13 |
Correct |
7009 ms |
21016 KB |
Output is correct |
| 14 |
Execution timed out |
8045 ms |
35856 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8038 ms |
21904 KB |
Time limit exceeded |
| 16 |
Execution timed out |
8026 ms |
25856 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8035 ms |
29164 KB |
Time limit exceeded |
