#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXR = 3e4 + 5;
const int MAGIC = 400;
const double eps = 1e-9;
int par[MAXN], col[MAXN], cnt[MAXN];
vi ans[MAXR];
vi adj[MAXN], ind[MAXR], idx[MAXR];
int n, r, q, t = 0, st[MAXN], en[MAXN];
//map<pii,int> dp;
void dfs(int u, int x, int d) {
int fl = 0;
if (col[u] == x)
fl++;
for (int v: adj[u])
dfs(v, x, d + fl);
ans[x][col[u]] += d;
}
void dfs(int u) {
st[u] = t++;
ind[col[u]].pb(st[u]);
idx[col[u]].pb(u);
for (int v: adj[u])
dfs(v);
en[u] = t;
}
int main() {
scanf("%d %d %d", &n, &r, &q);
scanf("%d", &col[0]);
for (int i = 1; i < n; i++) {
scanf("%d %d", &par[i], &col[i]);
adj[--par[i]].pb(i);
cnt[col[i]]++;
}
dfs(0);
for (int i = 1; i <= r; i++)
if (cnt[i] > MAGIC) {
ans[i].resize(r + 2);
dfs(0, i, 0);
}
while (q--) {
int x, y;
scanf("%d %d", &x, &y);
if (cnt[x] <= MAGIC) {
/*if (dp.count(mp(x, y))) {
printf("%d\n", dp[mp(x, y)]);
fflush(stdout);
continue;
}*/
int anscnt = 0;
for (int j = 0; j < idx[x].size(); j++) {
int lo = lower_bound(ind[y].begin(), ind[y].end(), st[idx[x][j]]) - ind[y].begin();
int hi = lower_bound(ind[y].begin(), ind[y].end(), en[idx[x][j]]) - ind[y].begin();
anscnt += hi - lo;
}
printf("%d\n", anscnt);
//dp[mp(x, y)] = anscnt;
fflush(stdout);
} else {
printf("%d\n", ans[x][y]);
fflush(stdout);
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < idx[x].size(); j++) {
~~^~~~~~~~~~~~~~~
regions.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &r, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &col[0]);
~~~~~^~~~~~~~~~~~~~~
regions.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &par[i], &col[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7040 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7168 KB |
Output is correct |
| 3 |
Correct |
9 ms |
7168 KB |
Output is correct |
| 4 |
Correct |
12 ms |
7168 KB |
Output is correct |
| 5 |
Correct |
11 ms |
7168 KB |
Output is correct |
| 6 |
Correct |
14 ms |
7168 KB |
Output is correct |
| 7 |
Correct |
30 ms |
7296 KB |
Output is correct |
| 8 |
Correct |
33 ms |
7216 KB |
Output is correct |
| 9 |
Correct |
40 ms |
7720 KB |
Output is correct |
| 10 |
Correct |
83 ms |
7680 KB |
Output is correct |
| 11 |
Correct |
82 ms |
7936 KB |
Output is correct |
| 12 |
Correct |
136 ms |
8448 KB |
Output is correct |
| 13 |
Correct |
195 ms |
8272 KB |
Output is correct |
| 14 |
Correct |
281 ms |
8832 KB |
Output is correct |
| 15 |
Correct |
296 ms |
10544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1831 ms |
11952 KB |
Output is correct |
| 2 |
Correct |
2543 ms |
11044 KB |
Output is correct |
| 3 |
Correct |
2796 ms |
13476 KB |
Output is correct |
| 4 |
Correct |
215 ms |
8832 KB |
Output is correct |
| 5 |
Correct |
363 ms |
9976 KB |
Output is correct |
| 6 |
Correct |
541 ms |
11768 KB |
Output is correct |
| 7 |
Correct |
1517 ms |
12456 KB |
Output is correct |
| 8 |
Correct |
1025 ms |
19448 KB |
Output is correct |
| 9 |
Correct |
2595 ms |
16760 KB |
Output is correct |
| 10 |
Correct |
3626 ms |
30804 KB |
Output is correct |
| 11 |
Correct |
5359 ms |
17292 KB |
Output is correct |
| 12 |
Correct |
1681 ms |
18548 KB |
Output is correct |
| 13 |
Correct |
2489 ms |
18552 KB |
Output is correct |
| 14 |
Correct |
3675 ms |
20480 KB |
Output is correct |
| 15 |
Correct |
3569 ms |
22344 KB |
Output is correct |
| 16 |
Correct |
4014 ms |
25792 KB |
Output is correct |
| 17 |
Correct |
3154 ms |
26632 KB |
Output is correct |
