#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);
fflush(stdout);
dp[mp(x, y)] = anscnt;
} else {
printf("%d\n", ans[x][y]);
fflush(stdout);
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:87:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < idx[x].size(); j++) {
~~^~~~~~~~~~~~~~~
regions.cpp:64:11: 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:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &col[0]);
~~~~~^~~~~~~~~~~~~~~
regions.cpp:67:12: 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:12: 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 |
9 ms |
7168 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7040 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7212 KB |
Output is correct |
| 4 |
Correct |
15 ms |
7168 KB |
Output is correct |
| 5 |
Correct |
12 ms |
7196 KB |
Output is correct |
| 6 |
Correct |
32 ms |
7416 KB |
Output is correct |
| 7 |
Correct |
30 ms |
7296 KB |
Output is correct |
| 8 |
Correct |
39 ms |
7472 KB |
Output is correct |
| 9 |
Correct |
59 ms |
7756 KB |
Output is correct |
| 10 |
Correct |
114 ms |
8176 KB |
Output is correct |
| 11 |
Correct |
198 ms |
8520 KB |
Output is correct |
| 12 |
Correct |
201 ms |
9300 KB |
Output is correct |
| 13 |
Correct |
211 ms |
8976 KB |
Output is correct |
| 14 |
Correct |
212 ms |
9680 KB |
Output is correct |
| 15 |
Correct |
299 ms |
11580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1269 ms |
13456 KB |
Output is correct |
| 2 |
Correct |
1519 ms |
12504 KB |
Output is correct |
| 3 |
Correct |
2112 ms |
17384 KB |
Output is correct |
| 4 |
Correct |
300 ms |
10512 KB |
Output is correct |
| 5 |
Correct |
448 ms |
12096 KB |
Output is correct |
| 6 |
Correct |
440 ms |
13852 KB |
Output is correct |
| 7 |
Correct |
801 ms |
13540 KB |
Output is correct |
| 8 |
Correct |
1462 ms |
22340 KB |
Output is correct |
| 9 |
Correct |
2597 ms |
25032 KB |
Output is correct |
| 10 |
Correct |
3579 ms |
37064 KB |
Output is correct |
| 11 |
Correct |
6384 ms |
28968 KB |
Output is correct |
| 12 |
Correct |
2131 ms |
22624 KB |
Output is correct |
| 13 |
Correct |
2446 ms |
24304 KB |
Output is correct |
| 14 |
Correct |
3463 ms |
26760 KB |
Output is correct |
| 15 |
Correct |
4259 ms |
31680 KB |
Output is correct |
| 16 |
Correct |
4165 ms |
35128 KB |
Output is correct |
| 17 |
Correct |
3379 ms |
35504 KB |
Output is correct |
