oj.uz

Submission #726583

# Submission time Handle Problem Language Result Execution time Memory
726583 2023-04-19T05:55:10 Z MadokaMagicaFan Prize (CEOI22_prize) C
100 / 100
 3055 ms 377376 KB 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 1000000
#define K 21
typedef long long ll;

int n, req;

typedef struct {
    int a, b;
    ll w;
} edge;

typedef struct{
    int ec;
    edge e[2*N+2];
    int in[N];
} edges;

typedef struct {
    int r;
    int j[N][K];
    int d[N], vis[N];
    ll h[N];
    edges *ne, *se;
} tree;

tree t1, t2;
int nodes[N], nc;
int ei[N], ec;

void
add_edge(edges *e, int a, int b, ll w)
{
    e->e[e->ec++] = (edge){a, b, w};
    e->e[e->ec++] = (edge){b, a, -w};
}

int
_sort_edge(const void *a, const void *b)
{
    return ((edge *)a)->a - ((edge *)b)->a;
}

void
edges_make(edges *e)
{
    int x, y;
    x = y = 0;
    qsort(e->e, e->ec, sizeof *(e->e), _sort_edge);
    while (x < n && y < e->ec) {
        if (x <= e->e[y].a)
            e->in[x++] = y;
        else
            ++y;
    }

    while (x < n)
        e->in[x++] = e->ec;
}

int
_sort_nodes(const void *a, const void *b)
{
    return ei[*(int *)a] - ei[*(int *)b];
}

void
tree_depth_dfs(tree *t, int x, int d)
{
    t->d[x] = d;
    if (t == &t1)
        nodes[nc++] = x;
    ei[x] = ec++;
    for (int i = t->ne->in[x]; i < t->ne->ec && t->ne->e[i].a == x; ++i) {
        if (t->ne->e[i].b == t->j[x][0]) continue;
        tree_depth_dfs(t, t->ne->e[i].b, d+1);
    }
    return;
}

void
tree_init(tree *t, int *p)
{
    int i, k;

    t->ne = malloc(sizeof *t->ne);
    t->se = malloc(sizeof *t->se);
    for (i = 0; i < n; ++i) {
        --p[i]; t->vis[i] = 0;
        if (p[i] == -2) {
            t->r = i;
            t->j[i][0] = i;
        } else {
            t->j[i][0] = p[i];
            add_edge(t->ne, i, p[i], -1);
        }
    }

    for (k = 1; k < K; ++k)
        for (i = 0; i < n; ++i)
            t->j[i][k] = t->j[t->j[i][k-1]][k-1];

    edges_make(t->ne);
    tree_depth_dfs(t, t->r, 0);
}

int
lca(tree *t, int a, int b)
{
    if (t->d[a] < t->d[b]) {
        a = a + b; b = a - b; a = a - b;
    }

    for (int k = K-1; k >= 0; --k) {
        if (t->d[t->j[a][k]] >= t->d[b])
            a = t->j[a][k];
    }

    assert(t->d[a] == t->d[b]);
    if (a == b) return a;
    for (int k = K-1; k >= 0; --k) {
        if (t->j[a][k] != t->j[b][k]) {
            a = t->j[a][k];
            b = t->j[b][k];
        }
    }
    return t->j[a][0];
}

void
con_depth(tree *t, int x, ll d)
{
    if (t->vis[x]) return;
    t->vis[x] = 1;

    t->h[x] = d;
    for (int i = t->se->in[x]; i < t->se->ec && t->se->e[i].a == x; ++i)
        con_depth(t, t->se->e[i].b, d + t->se->e[i].w);
    return;
}

ll ans[100000][2];

int
main(int argc, char *argv[])
{
    int q, t, i, x, y, z ,w, l;
    int p[N];
    scanf("%d %d %d %d\n", &n, &req, &q, &t);

    for (i = 0; i < n; ++i)
        scanf("%d", &p[i]);
    tree_init(&t1, p);

    for (i = 0; i < n; ++i)
        scanf("%d", &p[i]);
    ec = 0; tree_init(&t2, p);

    assert(nc == n);
    qsort(nodes, req, sizeof *nodes, _sort_nodes);

    for (i = 0; i < req; ++i)
        printf("%d ", nodes[i]+1);
    puts("");

    for (i = 0; i < req-1; ++i) {
        printf("? %d %d\n", nodes[i]+1, nodes[i+1]+1);
    }
    puts("!"); fflush(stdout);


    for (i = 0; i < req-1; ++i) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        l = lca(&t1, nodes[i], nodes[i+1]);
        add_edge(t1.se, nodes[i], l, -x);
        add_edge(t1.se, nodes[i+1], l, -y);
        l = lca(&t2, nodes[i], nodes[i+1]);
        add_edge(t2.se, nodes[i], l, -z);
        add_edge(t2.se, nodes[i+1], l, -w);
    }

    edges_make(t1.se);
    edges_make(t2.se);
    con_depth(&t1, nodes[i], 0);
    con_depth(&t2, nodes[i], 0);

    for (l = 0; l < t; ++l) {
        scanf("%d %d", &x, &y); --x; --y;
        ans[l][0] = t1.h[x] + t1.h[y] - 2ll * t1.h[lca(&t1, x, y)];
        ans[l][1] = t2.h[x] + t2.h[y] - 2ll * t2.h[lca(&t2, x, y)];
    }

    for (l = 0; l < t; ++l) {
        printf("%lld %lld\n", ans[l][0], ans[l][1]);
    }
    fflush(stdout);
}

Compilation message

Main.c: In function 'main':
Main.c:152:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |     scanf("%d %d %d %d\n", &n, &req, &q, &t);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:155:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         scanf("%d", &p[i]);
      |         ^~~~~~~~~~~~~~~~~~
Main.c:159:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         scanf("%d", &p[i]);
      |         ^~~~~~~~~~~~~~~~~~
Main.c:176:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         scanf("%d %d %d %d", &x, &y, &z, &w);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:191:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         scanf("%d %d", &x, &y); --x; --y;
      |         ^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1523 ms 194180 KB Output is correct
2 Correct 1520 ms 197364 KB Output is correct
3 Correct 1100 ms 171032 KB Output is correct
4 Correct 1112 ms 170452 KB Output is correct
5 Correct 1268 ms 173460 KB Output is correct
6 Correct 1410 ms 176448 KB Output is correct
7 Correct 1512 ms 176500 KB Output is correct
8 Correct 1438 ms 175724 KB Output is correct
9 Correct 1062 ms 170800 KB Output is correct
10 Correct 1310 ms 172920 KB Output is correct
11 Correct 1040 ms 169160 KB Output is correct
12 Correct 1130 ms 172308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1786 ms 197188 KB Output is correct
2 Correct 1555 ms 192408 KB Output is correct
3 Correct 1155 ms 170992 KB Output is correct
4 Correct 1223 ms 173756 KB Output is correct
5 Correct 1179 ms 171784 KB Output is correct
6 Correct 1574 ms 173564 KB Output is correct
7 Correct 1753 ms 176940 KB Output is correct
8 Correct 1767 ms 177252 KB Output is correct
9 Correct 1549 ms 177808 KB Output is correct
10 Correct 1543 ms 178848 KB Output is correct
11 Correct 1425 ms 174724 KB Output is correct
12 Correct 1517 ms 178620 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 178596 KB Output is correct
2 Correct 961 ms 178692 KB Output is correct
3 Correct 791 ms 155512 KB Output is correct
4 Correct 763 ms 155672 KB Output is correct
5 Correct 777 ms 155764 KB Output is correct
6 Correct 924 ms 159996 KB Output is correct
7 Correct 908 ms 159912 KB Output is correct
8 Correct 913 ms 160152 KB Output is correct
9 Correct 958 ms 159972 KB Output is correct
10 Correct 837 ms 159896 KB Output is correct
11 Correct 880 ms 159880 KB Output is correct
12 Correct 877 ms 159980 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2324 ms 356636 KB Output is correct
2 Correct 2347 ms 356716 KB Output is correct
3 Correct 1705 ms 311296 KB Output is correct
4 Correct 1701 ms 311048 KB Output is correct
5 Correct 1708 ms 310968 KB Output is correct
6 Correct 2418 ms 319928 KB Output is correct
7 Correct 2094 ms 319984 KB Output is correct
8 Correct 2196 ms 319824 KB Output is correct
9 Correct 2023 ms 320204 KB Output is correct
10 Correct 1951 ms 319828 KB Output is correct
11 Correct 2037 ms 319504 KB Output is correct
12 Correct 2043 ms 320012 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3055 ms 377376 KB Output is correct
2 Correct 2993 ms 376704 KB Output is correct
3 Correct 1976 ms 326884 KB Output is correct
4 Correct 2071 ms 331360 KB Output is correct
5 Correct 2082 ms 325908 KB Output is correct
6 Correct 2981 ms 339200 KB Output is correct
7 Correct 2622 ms 334560 KB Output is correct
8 Correct 2875 ms 337344 KB Output is correct
9 Correct 2460 ms 336968 KB Output is correct
10 Correct 2424 ms 335748 KB Output is correct
11 Correct 2410 ms 335824 KB Output is correct
12 Correct 2484 ms 338040 KB Output is correct