Submission #1176646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176646		KindaNameless	Islands (IOI08_islands)	C++20	24 / 100	203 ms	131720 KiB

islands

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

#define ll long long
#define ld long double

const int LIM = 1e6;

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

void add_edge(int u, int v, int w) {
    if(adj[u][0].first == 0) {
        adj[u][0] = make_pair(v, w);
    }
    else if(adj[u][1].first == 0) {
        adj[u][1] = make_pair(v, w);
    }
    else {
        adj[u][2] = make_pair(v, w);
    }
}

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(int it = 0; it < 3; ++it) {
        if(adj[cur][it].first == 0)break;

        if(adj[cur][it].first == par) {
            if(length_two_cycle[cur] && length_two_cycle[par]) {
                cycle.push_back(st.back()); cycle_weight.push_back(weight.back()); part_of_cycle[st.back()] = 1;
                cycle.push_back(adj[cur][it].first); cycle_weight.push_back(adj[cur][it].second); part_of_cycle[adj[cur][it].first] = 1;
                return 1;
            }
            continue;
        }
        if(!vis[adj[cur][it].first]) {
            if(dfs_cycle(adj[cur][it].first, cur, adj[cur][it].second)) {
                return 1;
            }
        }
        else if(vis_cycle[adj[cur][it].first]) {
            while(st.back() != adj[cur][it].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[adj[cur][it].first] = 1;
            cycle.push_back(adj[cur][it].first); cycle_weight.push_back(adj[cur][it].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(int it = 0; it < 3; ++it) {
        if(adj[cur][it].first == 0)break;

        if(part_of_cycle[adj[cur][it].first] || adj[cur][it].first == par)continue;

        ll length = dfs(adj[cur][it].first, cur, adj[cur][it].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];
        add_edge(i, to[i], L[i]);

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

    for(int i = 1; i <= N; ++i) {
        add_edge(to[i], 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: 24 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10