oj.uz

Submission #967584

# Submission time Handle Problem Language Result Execution time Memory
967584 2024-04-22T13:12:24 Z sleepntsheep Regions (IOI09_regions) C
35 / 100
 3726 ms 64592 KB 
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#define N 200000
#define R 25000

#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;
    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

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 3 ms 6740 KB Output is correct
5 Correct 4 ms 6488 KB Output is correct
6 Correct 9 ms 6488 KB Output is correct
7 Correct 14 ms 6488 KB Output is correct
8 Correct 19 ms 6488 KB Output is correct
9 Correct 26 ms 7008 KB Output is correct
10 Correct 41 ms 6744 KB Output is correct
11 Correct 75 ms 6816 KB Output is correct
12 Correct 87 ms 7176 KB Output is correct
13 Correct 145 ms 6744 KB Output is correct
14 Correct 214 ms 7016 KB Output is correct
15 Correct 340 ms 10036 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 948 ms 8652 KB Output isn't correct
2 Incorrect 1053 ms 8248 KB Output isn't correct
3 Incorrect 1968 ms 10392 KB Output isn't correct
4 Correct 180 ms 7264 KB Output is correct
5 Correct 251 ms 8716 KB Output is correct
6 Incorrect 319 ms 20952 KB Output isn't correct
7 Incorrect 1095 ms 27776 KB Output isn't correct
8 Incorrect 580 ms 32064 KB Output isn't correct
9 Correct 1784 ms 10924 KB Output is correct
10 Incorrect 2511 ms 57736 KB Output isn't correct
11 Correct 3726 ms 10836 KB Output is correct
12 Incorrect 1093 ms 40468 KB Output isn't correct
13 Incorrect 1467 ms 41280 KB Output isn't correct
14 Incorrect 1356 ms 46552 KB Output isn't correct
15 Incorrect 2597 ms 57040 KB Output isn't correct
16 Incorrect 2679 ms 64592 KB Output isn't correct
17 Incorrect 2166 ms 56464 KB Output isn't correct