Submission #1036345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036345		sleepntsheep	Training (IOI07_training)	C11	20 / 100	5 ms	604 KiB

training

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9