#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 = 1000;
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 |
208 KB |
Output is correct |
| 3 |
Correct |
3 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Correct |
7 ms |
464 KB |
Output is correct |
| 6 |
Correct |
20 ms |
1872 KB |
Output is correct |
| 7 |
Correct |
27 ms |
2128 KB |
Output is correct |
| 8 |
Correct |
24 ms |
3612 KB |
Output is correct |
| 9 |
Correct |
127 ms |
12572 KB |
Output is correct |
| 10 |
Correct |
86 ms |
34008 KB |
Output is correct |
| 11 |
Correct |
180 ms |
33188 KB |
Output is correct |
| 12 |
Correct |
610 ms |
72604 KB |
Output is correct |
| 13 |
Correct |
107 ms |
66180 KB |
Output is correct |
| 14 |
Correct |
225 ms |
49692 KB |
Output is correct |
| 15 |
Correct |
5850 ms |
80612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8026 ms |
122720 KB |
Time limit exceeded |
| 2 |
Runtime error |
847 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
4869 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
133 ms |
131072 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
259 ms |
131072 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
130 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
164 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
425 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
297 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
139 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
123 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
197 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
267 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
197 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
465 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
683 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
376 ms |
131072 KB |
Execution killed with signal 9 |
