Submission #967582

#	Time	Username	Problem	Language	Result	Execution time	Memory
967582		sleepntsheep	Regions (IOI09_regions)	C11	18 / 100	1193 ms	20116 KiB

regions

#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 (stderr)

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);
      |         ^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 15
• Subtask 2: 5 / 85