oj.uz

답안 #967579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967579 2024-04-22T13:08:52 Z sleepntsheep Regions (IOI09_regions) C
18 / 100
 1291 ms 51208 KB 
#include <stdio.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];

long long 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];
    }

    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("%lld\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("%lld\n",answer);
        }
        fflush(stdout);
    }
}

Compilation message

regions.c: In function 'push':
regions.c:14:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |     else if(!(o&o-1)) eh[i]=(int*)realloc(eh[i],2*sizeof**eh*o);
      |                 ~^~
regions.c: In function 'main':
regions.c:51:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d%d", &n, &r, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:53:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d", color);
      |     ^~~~~~~~~~~~~~~~~~
regions.c:58:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d%d", pp + i, color + i);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:72:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d%d", &r1, &r2);
      |         ^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 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 5 ms 8536 KB Output is correct
6 Correct 11 ms 8536 KB Output is correct
7 Correct 14 ms 8536 KB Output is correct
8 Correct 17 ms 8536 KB Output is correct
9 Correct 24 ms 8792 KB Output is correct
10 Correct 50 ms 8628 KB Output is correct
11 Correct 82 ms 8792 KB Output is correct
12 Correct 79 ms 8880 KB Output is correct
13 Correct 131 ms 8792 KB Output is correct
14 Incorrect 176 ms 8884 KB Output isn't correct
15 Incorrect 112 ms 11440 KB Output isn't correct

Subtask #2
5.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 437 ms 9640 KB Output isn't correct
2 Incorrect 551 ms 9004 KB Output isn't correct
3 Incorrect 821 ms 10904 KB Output isn't correct
4 Incorrect 173 ms 14168 KB Output isn't correct
5 Correct 244 ms 10416 KB Output is correct
6 Incorrect 329 ms 18352 KB Output isn't correct
7 Incorrect 506 ms 22708 KB Output isn't correct
8 Incorrect 559 ms 26804 KB Output isn't correct
9 Incorrect 1186 ms 30364 KB Output isn't correct
10 Runtime error 370 ms 44832 KB Execution killed with signal 13
11 Runtime error 224 ms 39404 KB Execution killed with signal 13
12 Incorrect 639 ms 30696 KB Output isn't correct
13 Incorrect 754 ms 31768 KB Output isn't correct
14 Incorrect 950 ms 35428 KB Output isn't correct
15 Runtime error 255 ms 42136 KB Execution killed with signal 13
16 Runtime error 759 ms 51208 KB Execution killed with signal 13
17 Incorrect 1291 ms 45352 KB Output isn't correct