#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)]);
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;
} else {
printf("%d\n", ans[x][y]);
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:86: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 |
Execution timed out |
7 ms |
7040 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
9 ms |
7040 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
8 ms |
7036 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
8 ms |
7168 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
7 ms |
7172 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
7 ms |
7168 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
8 ms |
7168 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
7 ms |
7168 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
10 ms |
7680 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
12 ms |
7680 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
17 ms |
7936 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
15 ms |
8448 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
19 ms |
8184 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
20 ms |
8752 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
21 ms |
10492 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
66 ms |
11816 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
65 ms |
10872 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
55 ms |
13432 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
24 ms |
8952 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
21 ms |
9984 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
144 ms |
11816 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
105 ms |
12372 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
172 ms |
19452 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
90 ms |
16808 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
463 ms |
30840 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
102 ms |
17144 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
258 ms |
18756 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
146 ms |
18756 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
811 ms |
20236 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
126 ms |
22312 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
112 ms |
25772 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
200 ms |
26616 KB |
Time limit exceeded (wall clock) |
