oj.uz

Submission #967588

# Submission time Handle Problem Language Result Execution time Memory
967588 2024-04-22T13:16:40 Z sleepntsheep Regions (IOI09_regions) C
100 / 100
 3885 ms 78492 KB 
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#define N 300000
#define R 35000

#define B 550

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;
    assert(i < N);
    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)
        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:54:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d%d%d", &n, &r, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:56:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", color);
      |     ^~~~~~~~~~~~~~~~~~
regions.c:61:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d", pp + i, color + i);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:74:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d%d", &r1, &r2);
      |         ^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10584 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 6 ms 10584 KB Output is correct
6 Correct 11 ms 10584 KB Output is correct
7 Correct 14 ms 10584 KB Output is correct
8 Correct 19 ms 10584 KB Output is correct
9 Correct 31 ms 10840 KB Output is correct
10 Correct 54 ms 10840 KB Output is correct
11 Correct 75 ms 10840 KB Output is correct
12 Correct 93 ms 11104 KB Output is correct
13 Correct 122 ms 10840 KB Output is correct
14 Correct 225 ms 10932 KB Output is correct
15 Correct 302 ms 13664 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1484 ms 12468 KB Output is correct
2 Correct 1717 ms 11864 KB Output is correct
3 Correct 2717 ms 13748 KB Output is correct
4 Correct 170 ms 10932 KB Output is correct
5 Correct 234 ms 12464 KB Output is correct
6 Correct 1086 ms 11440 KB Output is correct
7 Correct 1329 ms 11608 KB Output is correct
8 Correct 1062 ms 15716 KB Output is correct
9 Correct 1822 ms 12952 KB Output is correct
10 Correct 3885 ms 17816 KB Output is correct
11 Correct 3777 ms 12448 KB Output is correct
12 Correct 1131 ms 48048 KB Output is correct
13 Correct 1540 ms 49048 KB Output is correct
14 Correct 1674 ms 56736 KB Output is correct
15 Correct 2637 ms 71320 KB Output is correct
16 Correct 2952 ms 78492 KB Output is correct
17 Correct 2506 ms 66716 KB Output is correct