oj.uz

답안 #1036345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036345 2024-07-27T09:39:46 Z sleepntsheep Training (IOI07_training) C
20 / 100
 5 ms 604 KB 
#include <stdio.h>
#include <stdlib.h>

#define M 5005
#define N 1005


int n, m, m_, *eh[N], eo[N], dep[N], tin[N], head[N], tout[N];
int *fh[N], fo[N];

void pus_(int **eh, int *eo, int j) {
    int o = eo[0]++;
    if (0 == o) eh[0] = (int*)malloc(2 * sizeof **eh);
    else if (0 == (o & o - 1)) eh[0] = (int*)realloc(eh[0], 2 * o * sizeof**eh);
    eh[0][o] = j;
}
#define pus(eh, eo, j) pus_(&(eh), &(eo), j)

int rc[M], ru[M], rv[M], timer, sz[N], par[N], temp;

void dfs(int u, int p) {
    sz[u] = 1;
    par[u] = p;
    for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != p) {
        dep[v] = dep[u] + 1;
        dfs(v, u);
        if (sz[v] > sz[eh[u][0]]) temp = eh[u][0], eh[u][0] = eh[u][j], eh[u][j] = temp;
    }
}

void hld(int u) {
    tin[u] = timer++;
    for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != par[u]) {
        head[v] = j ? v : head[u];
        hld(v);
    }
    tout[u] = timer - 1;
}

int lca(int u, int v) {
    while (head[u] != head[v]) {
        if (dep[head[u]] > dep[head[v]]) u = par[head[u]];
        else v = par[head[v]];
    }
    return dep[u] < dep[v] ? u : v;
}

long long dp[N], dpc[N];

long long st1[N], st2[N];
void add(long long *st, int p, long long k) {
    for (st[p += n] += k; p /= 2;)
        st[p] = st[p * 2] + st[p * 2 + 1];
}
long long sum(long long *st, int l, int r) {
    long long z = 0;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
        if (l & 1) z += st[l++];
        if (r & 1) z += st[--r];
    }
    return z;
}

long long upqry(long long *st, int u, int a, int off) {
    long long z = 0;
    for (; head[u] != head[a]; u = par[head[u]])
        z += sum(st, tin[head[u]], tin[u]);
    z += sum(st, tin[a] + off, tin[u]);
    return z;
}

void efs(int u, int p) {
    dp[u] = 0;
    for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != par[u]) {
        efs(v, u);
        dp[u] += dp[v];
    }
    dpc[u] = dp[u];

    add(st1, tin[u], dpc[u]);

    for (int j = 0; j < fo[u]; ++j) {
        int e = fh[u][j];

        if (dep[ru[e]] > dep[rv[e]])
            temp = ru[e], ru[e] = rv[e], rv[e] = temp;

        long long here;

        if (tin[ru[e]] <= tin[rv[e]] && tout[rv[e]] <= tout[ru[e]]) {
            here = upqry(st1, rv[e], u, 0) - upqry(st2, rv[e], u, 1) + rc[e]
                + dp[rv[e]] - dpc[rv[e]];
        } else {
            here = upqry(st1, ru[e], u, 0) + upqry(st1, rv[e], u, 1)
                - upqry(st2, ru[e], u, 1) - upqry(st2, rv[e], u, 1) + rc[e]
                + dp[rv[e]] - dpc[rv[e]]
                + dp[ru[e]] - dpc[ru[e]];
        }

        if (here > dp[u]) {
            dp[u] = here;
        }
    }

    add(st2, tin[u], dp[u]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int u, v, c, i = 0; i < m; ++i) {
        scanf("%d%d%d", &u, &v, &c);
        if (!c)
            pus(eh[u], eo[u], v), pus(eh[v], eo[v], u);
        else
            ru[m_] = u, rv[m_] = v, rc[m_] = c, ++m_;
    }

    dfs(1, 1);
    head[1] = 1;
    hld(1);

    long long answer = 0;
    for (int i = 0; i < m_; ++i) {
        int a = lca(ru[i], rv[i]);
        answer += rc[i];
        if ((dep[ru[i]] + dep[rv[i]] - 2 * dep[a]) % 2) {
        } else {
            pus(fh[a], fo[a], i);
        }
    }

    efs(1, 1);
    printf("%lld\n", answer - dp[1]);

}

Compilation message

training.c: In function 'pus_':
training.c:14:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |     else if (0 == (o & o - 1)) eh[0] = (int*)realloc(eh[0], 2 * o * sizeof**eh);
      |                        ~~^~~
training.c: In function 'main':
training.c:109:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d%d", &n, &m);
      |     ^~~~~~~~~~~~~~~~~~~~~
training.c:111:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d%d%d", &u, &v, &c);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -