oj.uz

답안 #852801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852801 2023-09-22T17:55:40 Z lorenzoferrari Islands (IOI08_islands) C++17
80 / 100
 260 ms 131072 KB 
// https://training.olinfo.it/#/task/islands/statement

/*
 *  Steps:
 *      - dfs & weighted dfs-tree
 *      - foreach cc, find the diameter of the dfs-tree
 *      - foreach cc, store the cycle as a successor graph
 *      - foreach node v in the cycle, recursively compute the height of its tree
 *      - sliding window to find the maximum values of:
 *          * max1 = height[v] + height[u] + dist(v, u)
 *          * max2 = height[v] + height[u] - dist(v, u)
 *      - cycle_path = max(max1, L + max2), where L is the total length of the cycle
 *      - add foreach cc max(diameter, cycle_path)
 */

#include "bits/stdc++.h"
using namespace std;
using LL = long long;

vector<vector<array<int, 3>>> adj;
vector<vector<array<int, 2>>> tree;
vector<array<int, 2>> par;
vector<bool> vis, cyc;
int cycle_node = -1;

void dfs(int v, int pi) {
    vis[v] = true;
    for (auto [u, w, i] : adj[v]) {
        if (i == pi) continue;   // deal with cycles of length 2
        if (!vis[u]) {
            par[u] = {v, w};
            tree[v].push_back({u, w});
            tree[u].push_back({v, w});
            dfs(u, i);
        } else if (vis[u] && cycle_node == -1) {
            cycle_node = v;
            par[u] = {v, w};
        }
    }
}

void find_diam(int v, int p, LL dist, array<LL, 2>& max_dist) {
    max_dist = max(max_dist, array<LL, 2>{dist, v});
    for (auto [u, w] : tree[v]) {
        if (u == p) continue;
        find_diam(u, v, dist + w, max_dist);
    }
}

LL height(int v, int p) {
    LL ans = 0;
    for (auto [u, w] : tree[v]) {
        if (u == p) continue;
        if (cyc[u]) continue;
        ans = max(ans, w + height(u, v));
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    adj.resize(n+1);
    tree.resize(n+1);
    par.resize(n+1);
    vis.resize(n+1);
    cyc.resize(n+1);
    for (int v = 1, u, w; v <= n; ++v) {
        cin >> u >> w;
        adj[v].push_back({u, w, v});
        adj[u].push_back({v, w, v});
    }

    LL ans = 0;
    for (int v = 1; v <= n; ++v) {
        if (!vis[v]) {
            // first dfs
            dfs(v, -1);

            // diameter
            array<LL, 2> max_dist{0, v};
            find_diam(v, -1, 0, max_dist);
            int u = max_dist[1];
            max_dist = {0, u};
            find_diam(u, -1, 0, max_dist);
            LL diameter = max_dist[0];

            // path traversing the cycle
            LL a = cycle_node;
            LL cycle_length = 0;
            while (par[a][0] != cycle_node) {
                cyc[a] = true;
                cycle_length += par[a][1];
                a = par[a][0];
            }
            cyc[a] = true;
            cycle_length += par[a][1];

            a = cycle_node;
            LL max1 = -1e9, max2 = -1e9;
            LL prv1 = height(a, -1);
            LL prv2 = prv1;
            while (par[a][0] != cycle_node) {
                auto [b, w] = par[a];
                prv1 += w;
                prv2 -= w;
                LL h = height(b, -1);
                max1 = max(max1, prv1 + h);
                max2 = max(max2, prv2 + h);
                prv1 = max(prv1, h);
                prv2 = max(prv2, h);
                a = b;
            }
            LL cycle_path = max(max1, cycle_length + max2);

            // increase the answer by the maximum path in the current cc
            ans += max(diameter, cycle_path);

            cycle_node = -1;    // reset
        }
    }

    cout << ans << "\n";
}

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2652 KB Output is correct
2 Correct 14 ms 7256 KB Output is correct
3 Correct 9 ms 3416 KB Output is correct
4 Correct 4 ms 1880 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 10064 KB Output is correct
2 Correct 33 ms 16696 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 31568 KB Output is correct
2 Correct 87 ms 38276 KB Output is correct
3 Correct 105 ms 54608 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 59472 KB Output is correct
2 Correct 189 ms 96592 KB Output is correct
3 Correct 224 ms 105560 KB Output is correct
4 Correct 260 ms 131072 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 228 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 256 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -