oj.uz

Submission #967591

# Submission time Handle Problem Language Result Execution time Memory
967591 2024-04-22T13:17:48 Z sleepntsheep Regions (IOI09_regions) C
100 / 100
 3739 ms 68168 KB 
#pragma GCC optimize("O3,unroll-loops")

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#define N 300000
#define R 35000

#define B 450

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:17:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |     else if(!(o&o-1)) eh[i]=(int*)realloc(eh[i],2*sizeof**eh*o);
      |                 ~^~
regions.c: In function 'main':
regions.c:56:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d%d%d", &n, &r, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:58:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d", color);
      |     ^~~~~~~~~~~~~~~~~~
regions.c:63:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 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 6 ms 8536 KB Output is correct
6 Correct 10 ms 8536 KB Output is correct
7 Correct 17 ms 8536 KB Output is correct
8 Correct 20 ms 8536 KB Output is correct
9 Correct 24 ms 9048 KB Output is correct
10 Correct 43 ms 8792 KB Output is correct
11 Correct 77 ms 8792 KB Output is correct
12 Correct 84 ms 9228 KB Output is correct
13 Correct 127 ms 8972 KB Output is correct
14 Correct 216 ms 9480 KB Output is correct
15 Correct 272 ms 11608 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1416 ms 10768 KB Output is correct
2 Correct 1592 ms 10452 KB Output is correct
3 Correct 2515 ms 12440 KB Output is correct
4 Correct 178 ms 9748 KB Output is correct
5 Correct 245 ms 10764 KB Output is correct
6 Correct 336 ms 23236 KB Output is correct
7 Correct 1153 ms 29972 KB Output is correct
8 Correct 730 ms 34188 KB Output is correct
9 Correct 1909 ms 12324 KB Output is correct
10 Correct 3073 ms 61496 KB Output is correct
11 Correct 3739 ms 12600 KB Output is correct
12 Correct 981 ms 41480 KB Output is correct
13 Correct 1564 ms 42616 KB Output is correct
14 Correct 1485 ms 48492 KB Output is correct
15 Correct 2521 ms 60900 KB Output is correct
16 Correct 2510 ms 68168 KB Output is correct
17 Correct 2425 ms 58428 KB Output is correct