oj.uz

Submission #233408

# Submission time Handle Problem Language Result Execution time Memory
233408 2020-05-20T12:39:28 Z dolphingarlic Islands (IOI08_islands) C++14
28 / 100
 657 ms 131076 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<pair<int, ll>> graph[1000001], stck, cycle;
ll discarded, ans = 0, cmp_ans, dp[1000001], p[4][1000001];
bool processed[1000001], on_stck[1000001], on_cycle[1000001];

bool find_cycle(int node, pair<int, ll> parent = {0, 0}) {
    on_stck[node] = true;
    for (pair<int, ll> i : graph[node]) if (i != parent) {
        stck.push_back({node, i.second});
        if (on_stck[i.first]) {
            cycle.push_back({i.first, 0});
            on_cycle[i.first] = true;
            while (stck.back().first != i.first) {
                cycle.push_back(stck.back());
                on_cycle[stck.back().first] = true;
                stck.pop_back();
            }
            discarded = stck.back().second;
            return true;
        }
        if (find_cycle(i.first, {node, i.second})) return true;
        stck.pop_back();
        on_stck[i.first] = false;
    }
    return false;
}

void calc_tree(int node, int parent = 0) {
    processed[node] = true;
    ll mx = 0, sc = 0;
    for (pair<int, ll> i : graph[node]) if (i.first != parent && !on_cycle[i.first]) {
        calc_tree(i.first, node);
        if (dp[i.first] + i.second > mx) sc = mx, mx = dp[i.first] + i.second;
        else if (dp[i.first] + i.second > sc) sc = dp[i.first] + i.second;
    }
    dp[node] = mx;
    cmp_ans = max(cmp_ans, mx + sc);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n + 1) {
        int v;
        ll l;
        cin >> v >> l;
        graph[i].push_back({v, l});
        graph[v].push_back({i, l});
    }

    FOR(i, 1, n + 1) if (!processed[i]) {
        stck.clear(); cycle.clear();
        find_cycle(i);

        cmp_ans = 0;
        int m = cycle.size();

        FOR(j, 1, m) p[0][j] = p[0][j - 1] + cycle[j].second;
        for (int j = m - 2; ~j; j--) p[1][j] = p[1][j + 1] + cycle[j + 1].second;

        FOR(j, 0, m) {
            calc_tree(cycle[j].first);
            p[2][j] = dp[cycle[j].first] - p[0][j];
            p[3][j] = dp[cycle[j].first] + p[0][j];
            p[4][j] = dp[cycle[j].first] + p[1][j];
        }

        ll mx = p[2][0];
        FOR(j, 1, m) {
            cmp_ans = max(cmp_ans, p[3][j] + mx);
            mx = max(mx, p[2][j]);
        }
        mx = p[4][m - 1];
        for (int j = m - 2; ~j; j--) {
            cmp_ans = max(cmp_ans, p[3][j] + mx + discarded);
            mx = max(mx, p[4][j]);
        }

        ans += cmp_ans;

        FOR(j, 0, 5) FOR(k, 0, m) p[j][k] = 0;
    }
    cout << ans;
    return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:71:16: warning: array subscript is above array bounds [-Warray-bounds]
             p[4][j] = dp[cycle[j].first] + p[1][j];
             ~~~^
islands.cpp:79:17: warning: array subscript is above array bounds [-Warray-bounds]
         mx = p[4][m - 1];
              ~~~^
islands.cpp:82:29: warning: array subscript is above array bounds [-Warray-bounds]
             mx = max(mx, p[4][j]);
                          ~~~^

Subtask #1
15.0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 47992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 18 ms 23936 KB Output is correct
3 Correct 18 ms 23936 KB Output is correct
4 Runtime error 45 ms 47992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 18 ms 23936 KB Output is correct
6 Runtime error 45 ms 48376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 46 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 18 ms 23808 KB Output is correct
9 Runtime error 46 ms 48384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 19 ms 23840 KB Output is correct
11 Runtime error 49 ms 48384 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 19 ms 24056 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 48760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 25592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31576 KB Output is correct
2 Correct 64 ms 34920 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 42480 KB Output is correct
2 Correct 122 ms 53732 KB Output is correct
3 Incorrect 159 ms 72040 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 56820 KB Output is correct
2 Correct 250 ms 98804 KB Output is correct
3 Correct 281 ms 112980 KB Output is correct
4 Runtime error 337 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 92732 KB Output is correct
2 Runtime error 657 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 441 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -