Submission #1125782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125782		SulA	Islands (IOI08_islands)	C++20	90 / 100	780 ms	141328 KiB

islands

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
template<typename T> using ordered_set = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()

vector<pair<int,int>> adj[1'000'000];
int par[1'000'000], len[1'000'000];

void dfs(int u);
pair<long long, long long> longest(int u, int p1, int p2) {
    long long mx1 = 0, mx2 = 0;
    long long dia = 0;
    for (auto [v, w] : adj[u]) if (v != p1 && v != p2) {
        auto [a, b] = longest(v, u, u);
        a += w;
        dia = max(dia, b);
        if (a >= mx1) {
            swap(mx1, mx2);
            mx1 = a;
        } else mx2 = max(mx2, a);
    }
    dia = max(dia, mx1 + mx2);
    return make_pair(mx1, dia);
}

long long solve_comp(int start) {
    int fast = start, slow = start;
    do {
        fast = par[par[fast]];
        slow = par[slow];
    } while (fast != slow);
    vector<int> cycle, lens;
    do {
        cycle.push_back(slow);
        lens.push_back(len[slow]);
        slow = par[slow];
    } while (fast != slow);
    int k = cycle.size();
    long long ans = 0;
    vector<long long> vals(cycle.size()), pref(cycle.size());
    for (int i = 0; i < k; i++) {
        auto [a, b] = longest(cycle[i], cycle[(i + 1) % k], cycle[(i - 1 + k) % k]);
        vals[i] = a;
        ans = max(ans, b);
    }
    for (int i = 1; i < k; i++)
        pref[i] = pref[i-1] + lens[i-1];
    // j -> i = vals[i] + vals[j] + pref[i] - pref[j] -> (vals[i] + pref[i]) + (vals[j] - pref[j])
    long long mx = -1e18;
    for (int i = 0; i < k; i++) {
        ans = max(ans, vals[i] + pref[i] + mx);
        mx = max(mx, vals[i] - pref[i]);
    }
    // i -> j = vals[i] + vals[j] + L - (pref[i] - pref[j]) -> L + (vals[i] - pref[i]) + (vals[j] + pref[j])
    long long L = accumulate(all(lens), 0LL);
    mx = -1e18;
    for (int i = 0; i < k; i++) {
        ans = max(ans, L + vals[i] - pref[i] + mx);
        mx = max(mx, vals[i] + pref[i]);
    }
    dfs(start);
    return ans;
}

void dfs(int u) {
    len[u] = -1;
    for (auto [v, w] : adj[u]) if (len[v] != -1) dfs(v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> par[i] >> len[i];
        par[i]--;
        adj[i].emplace_back(par[i], len[i]);
        adj[par[i]].emplace_back(i, len[i]);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) if (len[i] != -1) {
            ans += solve_comp(i);
        }
    cout << ans;
}

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10