Submission #337335

#	Time	Username	Problem	Language	Result	Execution time	Memory
337335		arbor	Islands (IOI08_islands)	C++17	100 / 100	912 ms	128372 KiB

islands

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 1e6 + 5;
int N;
pii nex[MN];
vector<pii> g[MN];
bool vis[MN], done[MN];
ll ps[2 * MN], mx[MN], mxd, add[2 * MN];

void go(int u) {
    done[u] = true;
    for (auto &[v, w] : g[u]) {
        if (done[v]) continue;
        go(v);
        mxd = max(mxd, mx[u] + w + mx[v]);
        mx[u] = max(mx[u], w + mx[v]);
    }
}

ll solve(int u) {
    mxd = 0;
    int sz = 0;
    for (; !vis[u]; u = nex[u].first) vis[u] = true;
    for (int v = nex[u].first; ; v = nex[v].first) {
        done[v] = true;
        if (v == u) break;
    }
    for (int v = nex[u].first; ; v = nex[v].first) {
        sz++;
        go(v);
        add[sz] = mx[v];
        ps[sz + 1] = ps[sz] + nex[v].second;
        if (v == u) break;
    }
    for (int i = sz + 1; i < 2 * sz; i++) {
        add[i] = add[i - sz];
        ps[i + 1] = ps[sz + 1] + ps[i + 1 - sz];
    }
    deque<pair<int, ll>> q;
    for (int i = 1; i < sz * 2; i++) {
        while (!q.empty() && q.front().first <= i - sz) q.pop_front();
        if (!q.empty()) mxd = max(mxd, add[i] + ps[i] + q.front().second);
        ll val = add[i] - ps[i];
        while (!q.empty() && q.back().second <= val) q.pop_back();
        q.emplace_back(i, val);
    }
    return mxd;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int u = 1; u <= N; u++) {
        int v, w; cin >> v >> w;
        nex[u] = {v, w};
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    ll ans = 0;
    for (int i = 1; i <= N; i++) if (!done[i]) ans += solve(i);
    cout << ans << '\n';
    return 0;
}

• 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: 10 / 10