#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define N 200000
#define R 25000
#define B 160
int *eh[R], eo[R];
void push(int i, int j)
{
int o=eo[i]++;
if(!o)eh[i]=(int*)realloc(eh[i],sizeof**eh*2);
else if(!(o&o-1)) eh[i]=(int*)realloc(eh[i],2*sizeof**eh*o);
eh[i][o]=j;
}
int n, r, q, color[N], i, ii, j, jj, pp[N], r1, r2, tin[N], tout[N], aux[N];
int frequency[R], heavy_id[R], heavy_col[B], iota;
int head[N], nxt[N], vv[N];
int on_heavy[R][B], answer;
void link(int u, int v)
{
static int i = 1;
nxt[i] = head[u];
vv[i] = v;
head[u] = i++;
}
void dfs(int u)
{
static int timer = 0, frequency_[R] = { 0 };
aux[tin[u] = timer++] = u;
++frequency_[color[u]];
for (int j = 0; j < iota; ++j)
if (heavy_col[j] != color[u])
on_heavy[color[u]][j] += frequency_[heavy_col[j]];
for (int j = head[u]; j; j = nxt[j]) if (vv[j] != pp[u])
dfs(vv[j]);
--frequency_[color[u]];
tout[u] = timer - 1;
}
int main()
{
scanf("%d%d%d", &n, &r, &q);
scanf("%d", color);
++frequency[--color[0]];
for (i = 1; i < n; ++i)
{
scanf("%d%d", pp + i, color + i);
link(--pp[i], i);
if (++frequency[--color[i]] == B)
{
heavy_col[heavy_id[color[i]] = iota++] = color[i];
assert(iota != B);
}
}
dfs(0);
for (i = 0; i < n; ++i)
if (frequency[color[aux[i]]] < B)
push(color[aux[i]], aux[i]);
for ( ; q--; )
{
scanf("%d%d", &r1, &r2);
--r1, --r2;
if (frequency[r1] >= B)
printf("%d\n", on_heavy[r2][heavy_id[r1]]);
else
{
answer = 0;
for (ii = 0; ii < eo[r1]; ++ii)
{
int in = tin[eh[r1][ii]], out = tout[eh[r1][ii]], lower, upper;
/* binary search to count how many nodes with region r2 is in the subtree */
lower = -1, upper = eo[r2];
while (upper - lower > 1)
{
int mid = lower + (upper - lower) / 2;
if (tin[eh[r2][mid]] > out) upper = mid;
else lower = mid;
}
answer += upper;
lower = -1, upper = eo[r2];
while (upper - lower > 1)
{
int mid = lower + (upper - lower) / 2;
if (tin[eh[r2][mid]] >= in) upper = mid;
else lower = mid;
}
answer -= upper;
}
printf("%d\n",answer);
}
fflush(stdout);
}
}
Compilation message
regions.c: In function 'push':
regions.c:15:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
15 | else if(!(o&o-1)) eh[i]=(int*)realloc(eh[i],2*sizeof**eh*o);
| ~^~
regions.c: In function 'main':
regions.c:52:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d%d", &n, &r, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:54:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d", color);
| ^~~~~~~~~~~~~~~~~~
regions.c:59:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d%d", pp + i, color + i);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:76:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d%d", &r1, &r2);
| ^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
5 ms |
4436 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4692 KB |
Output is correct |
| 7 |
Correct |
14 ms |
4440 KB |
Output is correct |
| 8 |
Correct |
22 ms |
4440 KB |
Output is correct |
| 9 |
Correct |
27 ms |
4952 KB |
Output is correct |
| 10 |
Correct |
45 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
74 ms |
4692 KB |
Output is correct |
| 12 |
Correct |
82 ms |
5188 KB |
Output is correct |
| 13 |
Correct |
128 ms |
4920 KB |
Output is correct |
| 14 |
Incorrect |
157 ms |
5196 KB |
Output isn't correct |
| 15 |
Runtime error |
12 ms |
9816 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
10344 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
14 ms |
10128 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
15 ms |
10440 KB |
Execution killed with signal 6 |
| 4 |
Incorrect |
155 ms |
8280 KB |
Output isn't correct |
| 5 |
Correct |
234 ms |
6756 KB |
Output is correct |
| 6 |
Incorrect |
367 ms |
10984 KB |
Output isn't correct |
| 7 |
Incorrect |
512 ms |
13616 KB |
Output isn't correct |
| 8 |
Incorrect |
552 ms |
17740 KB |
Output isn't correct |
| 9 |
Incorrect |
1193 ms |
20116 KB |
Output isn't correct |
| 10 |
Runtime error |
23 ms |
11920 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
21 ms |
11672 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
26 ms |
12384 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
32 ms |
12472 KB |
Execution killed with signal 6 |
| 14 |
Runtime error |
35 ms |
13580 KB |
Execution killed with signal 6 |
| 15 |
Runtime error |
36 ms |
12680 KB |
Execution killed with signal 6 |
| 16 |
Runtime error |
25 ms |
11860 KB |
Execution killed with signal 6 |
| 17 |
Runtime error |
32 ms |
12780 KB |
Execution killed with signal 6 |
