oj.uz

Submission #967592

# Submission time Handle Problem Language Result Execution time Memory
967592 2024-04-22T13:18:46 Z vjudge1 Regions (IOI09_regions) C
100 / 100
 3655 ms 68036 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 2 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 9 ms 8536 KB Output is correct
7 Correct 16 ms 8536 KB Output is correct
8 Correct 21 ms 8536 KB Output is correct
9 Correct 29 ms 9048 KB Output is correct
10 Correct 41 ms 8720 KB Output is correct
11 Correct 76 ms 8792 KB Output is correct
12 Correct 82 ms 9048 KB Output is correct
13 Correct 119 ms 8792 KB Output is correct
14 Correct 213 ms 9048 KB Output is correct
15 Correct 285 ms 11864 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1517 ms 10840 KB Output is correct
2 Correct 1573 ms 10328 KB Output is correct
3 Correct 2539 ms 12440 KB Output is correct
4 Correct 173 ms 9236 KB Output is correct
5 Correct 214 ms 10780 KB Output is correct
6 Correct 405 ms 23212 KB Output is correct
7 Correct 1127 ms 29692 KB Output is correct
8 Correct 706 ms 34644 KB Output is correct
9 Correct 1883 ms 12412 KB Output is correct
10 Correct 2853 ms 61624 KB Output is correct
11 Correct 3655 ms 12552 KB Output is correct
12 Correct 1014 ms 41684 KB Output is correct
13 Correct 1512 ms 42688 KB Output is correct
14 Correct 1606 ms 48304 KB Output is correct
15 Correct 2733 ms 60792 KB Output is correct
16 Correct 2788 ms 68036 KB Output is correct
17 Correct 2556 ms 58324 KB Output is correct