Submission #233409

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
233409	2020-05-20T12:39:58 Z	dolphingarlic	Islands (IOI08_islands)	C++14	48 / 100	608 ms	131072 KB

islands

#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[5][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;
}

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	19 ms	24064 KB	Output is correct
4	Runtime error	46 ms	47996 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Correct	19 ms	23936 KB	Output is correct
6	Runtime error	47 ms	48376 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	49 ms	48012 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	19 ms	23936 KB	Output is correct
9	Runtime error	47 ms	48376 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Correct	18 ms	24064 KB	Output is correct
11	Runtime error	56 ms	48576 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	18 ms	24064 KB	Output is correct
2	Correct	19 ms	24064 KB	Output is correct

Subtask #3
0 / 4.0

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

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	25472 KB	Output is correct
2	Correct	42 ms	29692 KB	Output is correct
3	Correct	31 ms	25600 KB	Output is correct
4	Correct	24 ms	24704 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	31212 KB	Output is correct
2	Correct	60 ms	33772 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	40304 KB	Output is correct
2	Correct	129 ms	52200 KB	Output is correct
3	Correct	153 ms	69644 KB	Output is correct

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	189 ms	51700 KB	Output is correct
2	Correct	242 ms	94920 KB	Output is correct
3	Correct	272 ms	109780 KB	Output is correct
4	Runtime error	334 ms	131072 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	379 ms	80572 KB	Output is correct
2	Runtime error	608 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	449 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Submission #233409

Compilation message