Submission #1176611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176611		KindaNameless	Islands (IOI08_islands)	C++20	80 / 100	325 ms	178416 KiB

islands

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

#define ll long long
#define ld long double

const int LIM = 1e6;

set<pair<int, int>> length_two_cycle;

vector<pair<int, int>> adj[LIM + 1];
vector<int> cycle, cycle_weight, st, weight;
bitset<LIM + 1> part_of_cycle, vis, vis_cycle;

bool dfs_cycle(int cur, int par = -1, int last_weight = 0) {
    vis[cur] = 1;
    vis_cycle[cur] = 1;
    st.push_back(cur); weight.push_back(last_weight);
    for(auto elem : adj[cur]) {
        if(elem.first == par) {
            if(length_two_cycle.count(make_pair(cur, par))) {
                cycle.push_back(st.back()); cycle_weight.push_back(weight.back()); part_of_cycle[st.back()] = 1;
                cycle.push_back(elem.first); cycle_weight.push_back(elem.second); part_of_cycle[elem.first] = 1;
                return 1;
            }
            continue;
        }
        if(!vis[elem.first]) {
            if(dfs_cycle(elem.first, cur, elem.second)) {
                return 1;
            }
        }
        else if(vis_cycle[elem.first]) {
            while(st.back() != elem.first) {
                cycle.push_back(st.back()); cycle_weight.push_back(weight.back());
                part_of_cycle[st.back()] = 1;
                st.pop_back(); weight.pop_back();
            }
            part_of_cycle[elem.first] = 1;
            cycle.push_back(elem.first); cycle_weight.push_back(elem.second);
            return 1;
        }
    }
    st.pop_back(); weight.pop_back();
    vis_cycle[cur] = 0;

    return 0;
}

ll max_length = 0;

ll dfs(int cur, int par = -1, int last_weight = 0) {
    vis[cur] = 1;
    ll first_max = 0, second_max = 0;

    for(auto elem : adj[cur]) {
        if(part_of_cycle[elem.first] || elem.first == par)continue;

        ll length = dfs(elem.first, cur, elem.second);

        if(length >= first_max) {
            second_max = first_max;
            first_max = length;
        }
        else if(length >= second_max) {
            second_max = length;
        }
    }
    max_length = max(max_length, first_max + second_max);

    return (ll)last_weight + first_max;
}

int to[LIM + 1], L[LIM + 1];
bitset<LIM + 1> need;

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

    for(int i = 1; i <= N; ++i) {
        cin >> to[i] >> L[i];
        adj[i].push_back(make_pair(to[i], L[i]));

        if(to[i] < i && to[to[i]] == i) {
            need[to[i]] = 0;
            length_two_cycle.insert(make_pair(i, to[i]));
            length_two_cycle.insert(make_pair(to[i], i));
        }
        else {
            need[i] = 1;
        }
    }

    for(int i = 1; i <= N; ++i) {
        adj[to[i]].push_back(make_pair(i, L[i]));
    }

    ll answer = 0;
    for(int i = 1; i <= N; ++i) {
        if(!vis[i]){
            vector<int>().swap(cycle);
            vector<int>().swap(st);
            vector<int>().swap(cycle_weight);
            vector<int>().swap(weight);

            dfs_cycle(i);

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

//            for(int j = 0; j < cycle.size(); ++j) {
//                cout << cycle[j] << " " << cycle_weight[j] << "\n";
//            }

            for(int elem : cycle_weight) {
                total_length += (ll)elem;
            }

            for(int j = 0; j < cycle.size(); ++j) {
                ll depth = dfs(cycle[j]);

                if(j > 0) {
                    max_length = max(max_length, regular_max + depth + current_length);
                    max_length = max(max_length, reverse_max + depth - current_length + total_length);
                }

                regular_max = max(regular_max, depth - current_length);
                reverse_max = max(reverse_max, depth + current_length);

                current_length += cycle_weight[j];

                //cout << "| " << cycle[j] << " " << current_length << " " << regular_max << " " << reverse_max << "\n";
            }

            //cout << max_length << "\n";

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