Submission #1036141

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1036141	2024-07-27T03:58:36 Z	thinknoexit	Islands (IOI08_islands)	C++17	100 / 100	682 ms	116320 KB

islands

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000001;
vector<pair<int, int>> adj[N];
int deg[N], lv[N];
bool cycle[N], vis[N];
ll dp[2][N], qs[N], a[N];
ll res = 0;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int a, x;
        cin >> a >> x;
        adj[i].push_back({ a, x });
        adj[a].push_back({ i, x });
        deg[i]++, deg[a]++;
    }
    // find cycle using kahn's algorithm
    {
        queue<int> q;
        for (int i = 1;i <= n;i++) {
            cycle[i] = 1;
            if (deg[i] == 1) q.push(i);
        }
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cycle[v] = 0;
            vis[v] = 1;
            for (auto& x : adj[v]) {
                if (!vis[x.first]) {
                    lv[x.first] = max(lv[x.first], lv[v] + 1);
                }
                if (--deg[x.first] == 1) q.push(x.first);
            }
        }
        memset(vis, 0, sizeof vis);
    }
    //for (int i = 1;i <= n;i++) cout << lv[i] << ' ';
    ll ans = 0;
    // for each component find the longest path and sum up to answer
    for (int i = 1;i <= n;i++) {
        if (!cycle[i] || vis[i]) continue;
        vector<pair<int, int>> c;
        c.push_back({ 0, 0 });
        int now = i, p = -1;
        while (1) {
            bool ch = 0;
            vis[now] = 1;
            for (auto& x : adj[now]) {
                if (!cycle[x.first] || x.first == p) continue;
                c.push_back({ now, x.second });
                if (!vis[x.first]) {
                    p = now;
                    ch = 1;
                    now = x.first;
                    break;
                }
            }
            if (!ch) {
                if ((int)c.size() == 2) { // parallel edge
                    multiset<int> s;
                    for (auto& x : adj[now]) {
                        if (!cycle[x.first]) continue;
                        s.insert(x.second);
                    }
                    s.erase(s.find(c.back().second));
                    c.push_back({ now, *s.begin() });
                }
                break;
            }
        }
        res = 0;
        // c is list of cycle in order
        { // dp on tree
            for (auto& x : c) vis[x.first] = 0;
            // bfs
            vector<int> nodes;
            queue<int> q;
            q.push(i), vis[i] = 1;
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                nodes.push_back(v);
                for (auto& x : adj[v]) if (!vis[x.first]) q.push(x.first), vis[x.first] = 1;
            }
            sort(nodes.begin(), nodes.end(), [&](int a, int b) {
                return lv[a] < lv[b];
                });
            for (auto& v : nodes) {
                dp[0][v] = dp[1][v] = 0;
                for (auto& x : adj[v]) {
                    if (lv[v] < lv[x.first] || cycle[x.first]) continue;
                    dp[1][v] = max(dp[1][v], dp[0][x.first] + x.second);
                    if (dp[1][v] > dp[0][v]) swap(dp[0][v], dp[1][v]);
                }
                res = max(res, dp[0][v] + dp[1][v]);
            }
        }
        int sz = c.size() - 1;
        for (int i = 1;i <= sz;i++) {
            qs[i] = qs[i - 1] + c[i - 1].second;
            a[i] = dp[0][c[i].first];
        }
        ll mx = -1e18, mx2 = -1e18;
        ll sk = c[sz].second;
        for (int i = 1;i <= sz;i++) {
            res = max(res, mx + qs[i] + a[i]);
            res = max(res, mx2 + qs[sz] - qs[i] + a[i] + sk);
            mx = max(mx, -qs[i] + a[i]);
            mx2 = max(mx2, qs[i] + a[i]);
        }
        ans += res;
        //cout << res << ' ';
    }
    cout << ans;
    return 0;
}

Subtask #1
33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	24920 KB	Output is correct
2	Correct	11 ms	24924 KB	Output is correct
3	Correct	11 ms	24916 KB	Output is correct
4	Correct	11 ms	24924 KB	Output is correct
5	Correct	11 ms	24768 KB	Output is correct
6	Correct	11 ms	24924 KB	Output is correct
7	Correct	11 ms	24764 KB	Output is correct
8	Correct	11 ms	24924 KB	Output is correct
9	Correct	11 ms	24920 KB	Output is correct
10	Correct	11 ms	24924 KB	Output is correct
11	Correct	11 ms	24984 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	24924 KB	Output is correct
2	Correct	11 ms	24924 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	24920 KB	Output is correct
2	Correct	13 ms	25176 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	25944 KB	Output is correct
2	Correct	27 ms	27604 KB	Output is correct
3	Correct	18 ms	26460 KB	Output is correct
4	Correct	13 ms	25692 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	28532 KB	Output is correct
2	Correct	29 ms	31280 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	38472 KB	Output is correct
2	Correct	67 ms	40068 KB	Output is correct
3	Correct	79 ms	44136 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	49072 KB	Output is correct
2	Correct	139 ms	62884 KB	Output is correct
3	Correct	139 ms	65952 KB	Output is correct
4	Correct	172 ms	73352 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	217 ms	96800 KB	Output is correct
2	Correct	558 ms	111988 KB	Output is correct
3	Correct	207 ms	85820 KB	Output is correct
4	Correct	278 ms	109180 KB	Output is correct
5	Correct	269 ms	109400 KB	Output is correct
6	Correct	678 ms	101980 KB	Output is correct
7	Correct	300 ms	116320 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	206 ms	84700 KB	Output is correct
2	Correct	229 ms	84760 KB	Output is correct
3	Correct	263 ms	115688 KB	Output is correct
4	Correct	266 ms	91728 KB	Output is correct
5	Correct	258 ms	112068 KB	Output is correct
6	Correct	323 ms	102464 KB	Output is correct
7	Correct	682 ms	103504 KB	Output is correct

Submission #1036141

Compilation message