Submission #1176694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176694		KindaNameless	Islands (IOI08_islands)	C++20	100 / 100	188 ms	38776 KiB

islands

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

const int LIM = 1e6;

pair<int, int> cycle_next[LIM + 1];
bitset<LIM + 1> vis1, vis2;
int to[LIM + 1], L[LIM + 1], deg[LIM + 1];
ll max_depth[LIM + 1], diameter[LIM + 1];

void solve() {
    int N; cin >> N;

    for(int i = 1; i <= N; ++i) {
        cin >> to[i] >> L[i];
        deg[to[i]]++;

        cycle_next[i] = make_pair(0, 0);
    }

    for(int i = 1; i <= N; ++i) {
        if(!vis1[i]) {
            int cur = i, weight = 0;
            vector<pair<int, int>> st;
            while(!vis1[cur]) {
                vis1[cur] = 1;
                st.push_back(make_pair(cur, weight));
                weight = L[cur];
                cur = to[cur];
            }

            if(!vis2[cur]) {
                int last = cur, first = st.back().first;
                while(st.back().first != last) {
                    pair<int, int> now = st.back(); st.pop_back();
                    cycle_next[now.first] = make_pair(st.back().first, now.second);
                }
                cycle_next[last] = make_pair(first, weight);
            }

            cur = i;
            while(!vis2[cur]) {
                vis2[cur] = 1;
                cur = to[cur];
            }
        }
    }

    queue<int> q;

    for(int i = 1; i <= N; ++i) {
        if(deg[i] == 0) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int cur = q.front(); q.pop();

        int nx = to[cur]; ll length = L[cur] + max_depth[cur];

        diameter[nx] = max(diameter[nx], diameter[cur]);
        diameter[nx] = max(diameter[nx], max_depth[nx] + length);
        max_depth[nx] = max(max_depth[nx], length);

        deg[nx]--;
        if(deg[nx] == 0) {
            q.push(nx);
        }
    }

    vis1 = 0;

    ll answer = 0;
    for(int i = 1; i <= N; ++i) {
        if(cycle_next[i].first == 0 || vis1[i]) {
            continue;
        }

        ll max_length = 0, total_length = 0, current_length = 0, regular_max = -1e18, reverse_max = -1e18;

        int pos = i;
        bool first = 1;
        while(first || pos != i) {
            if(first)first = 0;
            vis1[pos] = 1;
            max_length = max(max_length, diameter[pos]);
            total_length += (ll)cycle_next[pos].second;
            pos = cycle_next[pos].first;
        }

        pos = i;
        first = 1;
        while(first || pos != i) {

            if(!first) {
                max_length = max(max_length, regular_max + max_depth[pos] + current_length);
                max_length = max(max_length, reverse_max + max_depth[pos] - current_length + total_length);
            }
            else first = 0;

            regular_max = max(regular_max, max_depth[pos] - current_length);
            reverse_max = max(reverse_max, max_depth[pos] + current_length);

            current_length += (ll)cycle_next[pos].second;
            pos = cycle_next[pos].first;
        }

        answer += max_length;
    }

    cout << answer;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1; //cin >> tc;

    while(tc--) {
        solve();
    }

    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