Submission #1125735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125735		SulA	Islands (IOI08_islands)	C++20	64 / 100	347 ms	126424 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];
bool visited[1'000'000];

void dfs(int u);
long long longest(int u, int p1, int p2) {
    long long ans = 0;
    for (auto [v, w] : adj[u]) if (v != p1 && v != p2) {
        ans = max(ans, longest(v, u, u) + w);
    }
    return ans;
}

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();
    vector<long long> vals(cycle.size()), pref(cycle.size());
    for (int i = 0; i < k; i++)
        vals[i] = longest(cycle[i], cycle[(i+1) % k], cycle[(i-1+k) %  k]);
    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, ans = 0;
    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) {
    visited[u] = true;
    for (auto [v, w] : adj[u]) if (!visited[v]) 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 (!visited[i]) {
        ans += solve_comp(i);
    }
    cout << ans;
}

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