oj.uz

답안 #1036167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036167 2024-07-27T04:32:09 Z sleepntsheep Islands (IOI08_islands) C
64 / 100
 267 ms 131072 KB 
#include <stdio.h>

#define NN 1000001
#define MM 2000002

long long max(long long i, long long j) {return i > j ? i : j;} 

int n, ww[MM], to[MM], lnk[MM], head[NN], col[NN];

void link(int u, int v, int w) {
    static int ii = 0;
    int i = ++ii;
    to[i] = v;
    ww[i] = w;
    lnk[i] = head[u];
    head[u] = i;
}

int cycle_head, cycle_tail;
int cyc[NN], co, par[NN], incyc[NN];
long long tentacle[NN], tentacle2[NN], aa[NN], here;


int dfs(int u, int pe) {
    col[u] = 1;

    for (int j = head[u]; j; j = lnk[j]) if ((j + 1) / 2 - (pe + 1) / 2) {
        int v = to[j];
        if (col[v]) {
            cycle_head = u;
            cycle_tail = v;

            co = 0;
            int cur = u;
            for (; cur != v && cur != -1; cur = par[cur])
                incyc[cyc[co++] = cur] = 1;
            incyc[cyc[co++] = v] = 1;

            return 1;
        }
        par[v] = u;
        if (dfs(v, j))
            return 1;
    }
    return 0;
}

void dfs2(int u, int p) {
    col[u] = 1;
    for (int j = head[u]; j; j = lnk[j]) {
        int v = to[j];
        if (v == p || incyc[v]) continue;
        dfs2(v, u);

        if (tentacle2[v] + ww[j] >= tentacle[u])
            tentacle2[u] = tentacle[u], tentacle[u] = tentacle2[v] + ww[j];
        else if (tentacle2[v] + ww[j] >= tentacle2[u])
            tentacle2[u] = tentacle2[v] + ww[j];

        if (tentacle[v] + ww[j] >= tentacle[u])
            tentacle2[u] = tentacle[u], tentacle[u] = tentacle[v] + ww[j];
        else if (tentacle[v] + ww[j] >= tentacle2[u])
            tentacle2[u] = tentacle[v] + ww[j];

    }
    here = max(tentacle[u], tentacle2[u]);
}

long long answer = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1, j, k; i <= n; ++i)
        scanf("%d%d", &j, &k), link(i, j, k), link(j, i, k);

    for (int ii = 1; ii <= n; ++ii) {
        if (col[ii]) continue;

        par[ii] = -1;
        dfs(ii, -1);

        long long op0 = -1e18, op1 = -1e18;
        here = 0;

        long long cycle_w = 0;
        for (int i = 0; i < co; ++i) {
            for (int j = head[cyc[i]]; j; j = lnk[j])
                if (incyc[to[j]]) cycle_w += ww[j];
            dfs2(cyc[i], -1);
        }
        cycle_w /= 2;

        if (co == 2) {
            for (int j = head[cycle_head]; j; j = lnk[j])
                if (cycle_tail == to[j])
                    here = max(here, ww[j]+ tentacle[cycle_tail] + tentacle[cycle_head]);

            answer += here;
            continue;
        }

        for (int i = 0; i < co; ++i) {
            here = max(here, tentacle[cyc[i]] + max(aa[i] + op0, -aa[i] + op1));

            op0 = max(tentacle[cyc[i]] - aa[i], op0);
            op1 = max(tentacle[cyc[i]] + cycle_w + aa[i], op1);

            if (i + 1 < co)
                for (int j = head[cyc[i]]; j; j = lnk[j])
                    if (to[j] == cyc[i + 1]) {
                        aa[i + 1] = aa[i] + ww[j];
                        break;
                    }

        }

        answer += here;
    }
    printf("%lld\n", answer);
}

Compilation message

islands.c: In function 'main':
islands.c:72:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
islands.c:74:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d%d", &j, &k), link(i, j, k), link(j, i, k);
      |         ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Incorrect 0 ms 4444 KB Output isn't correct
11 Correct 1 ms 4444 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 10 ms 5212 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Incorrect 3 ms 4956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 6236 KB Output is correct
2 Correct 15 ms 9364 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 13208 KB Output is correct
2 Correct 36 ms 16208 KB Output is correct
3 Correct 49 ms 25360 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 22356 KB Output is correct
2 Correct 115 ms 42620 KB Output is correct
3 Correct 113 ms 44700 KB Output is correct
4 Correct 121 ms 64168 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 267 ms 131072 KB Output is correct
2 Incorrect 211 ms 90196 KB Output isn't correct
3 Halted 0 ms 0 KB -