제출 #1176597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176597		KindaNameless	Islands (IOI08_islands)	C++20	70 / 100	607 ms	196608 KiB

islands

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

#define ll long long
#define ld long double

#define int long long

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;
bool part_of_cycle[LIM + 1], vis[LIM + 1];
int vis_cycle[LIM + 1];
ll max_length = 0;

bool dfs_cycle(int cur, int par = -1, int last_weight = 0) {
    vis_cycle[cur]++;
    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_cycle[elem.first]) {
            if(dfs_cycle(elem.first, cur, elem.second)) {
                return 1;
            }
        }
        else if(vis_cycle[elem.first] == 1) {
            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]++;

    return 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;
}

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

    map<pair<int, int>, int> to_add;
    for(int i = 1; i <= N; ++i) {
        int u, l; cin >> u >> l;
        adj[i].push_back(make_pair(u, l));

        if(to_add.count(make_pair(i, u))) {
            to_add.erase(make_pair(i, u));
            length_two_cycle.insert(make_pair(i, u));
            length_two_cycle.insert(make_pair(u, i));
        }
        else {
            to_add[make_pair(u, i)] = l;
        }
    }

    for(auto elem : to_add) {
        adj[elem.first.first].push_back(make_pair(elem.first.second, elem.second));
    }

    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;
}

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