#include <stdio.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];
long long 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];
}
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("%lld\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("%lld\n",answer);
}
fflush(stdout);
}
}
Compilation message
regions.c: In function 'push':
regions.c:14:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
14 | else if(!(o&o-1)) eh[i]=(int*)realloc(eh[i],2*sizeof**eh*o);
| ~^~
regions.c: In function 'main':
regions.c:51:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%d%d", &n, &r, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:53:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d", color);
| ^~~~~~~~~~~~~~~~~~
regions.c:58:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d%d", pp + i, color + i);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:72:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d", &r1, &r2);
| ^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8536 KB |
Output is correct |
| 4 |
Correct |
3 ms |
8536 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8536 KB |
Output is correct |
| 6 |
Correct |
11 ms |
8536 KB |
Output is correct |
| 7 |
Correct |
14 ms |
8536 KB |
Output is correct |
| 8 |
Correct |
17 ms |
8536 KB |
Output is correct |
| 9 |
Correct |
24 ms |
8792 KB |
Output is correct |
| 10 |
Correct |
50 ms |
8628 KB |
Output is correct |
| 11 |
Correct |
82 ms |
8792 KB |
Output is correct |
| 12 |
Correct |
79 ms |
8880 KB |
Output is correct |
| 13 |
Correct |
131 ms |
8792 KB |
Output is correct |
| 14 |
Incorrect |
176 ms |
8884 KB |
Output isn't correct |
| 15 |
Incorrect |
112 ms |
11440 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
437 ms |
9640 KB |
Output isn't correct |
| 2 |
Incorrect |
551 ms |
9004 KB |
Output isn't correct |
| 3 |
Incorrect |
821 ms |
10904 KB |
Output isn't correct |
| 4 |
Incorrect |
173 ms |
14168 KB |
Output isn't correct |
| 5 |
Correct |
244 ms |
10416 KB |
Output is correct |
| 6 |
Incorrect |
329 ms |
18352 KB |
Output isn't correct |
| 7 |
Incorrect |
506 ms |
22708 KB |
Output isn't correct |
| 8 |
Incorrect |
559 ms |
26804 KB |
Output isn't correct |
| 9 |
Incorrect |
1186 ms |
30364 KB |
Output isn't correct |
| 10 |
Runtime error |
370 ms |
44832 KB |
Execution killed with signal 13 |
| 11 |
Runtime error |
224 ms |
39404 KB |
Execution killed with signal 13 |
| 12 |
Incorrect |
639 ms |
30696 KB |
Output isn't correct |
| 13 |
Incorrect |
754 ms |
31768 KB |
Output isn't correct |
| 14 |
Incorrect |
950 ms |
35428 KB |
Output isn't correct |
| 15 |
Runtime error |
255 ms |
42136 KB |
Execution killed with signal 13 |
| 16 |
Runtime error |
759 ms |
51208 KB |
Execution killed with signal 13 |
| 17 |
Incorrect |
1291 ms |
45352 KB |
Output isn't correct |
