Submission #219609

#	Time	Username	Problem	Language	Result	Execution time	Memory
219609		tatyam	Islands (IOI08_islands)	C++17	37 / 100	670 ms	131076 KiB

islands

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 0x1fffffffffffffff;
#define name3(a,b,c,d,...) d
#define rep1(a) for(ll i = 0; i < a; i++)
#define rep3(i,a,b) for(ll i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(a) for(ll i = a; i--; )
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
 
 
ll n, ans = 0;
vector<bool> used;
vector<vector<pll>> g;
ll Diameter(ll at){
    unordered_map<ll, ll> cost;
    cost[at] = 0;
    vector<ll> q = {at};
    while(q.size()){
        ll at = q.back();
        q.pop_back();
        each(i, g[at]){
            cost.try_emplace(i.first, INF);
            if(chmin(cost[i.first], cost[at] + i.second)) q.push_back(i.first);
        }
    }
    ll d1 = -1, max = 0;
    each(i, cost) if(chmax(max, i.second)) d1 = i.first;
    cost.clear();
    cost[d1] = 0;
    q = {d1};
    while(q.size()){
        ll at = q.back();
        q.pop_back();
        each(i, g[at]){
            cost.try_emplace(i.first, INF);
            if(chmin(cost[i.first], cost[at] + i.second)) q.push_back(i.first);
        }
    }
    max = 0;
    each(i, cost) chmax(max, i.second);
    return max;
}
void solve(ll start){
    if(used[start]) return;
    vector<ll> list = {start};
    used[start] = 1;
    rep(list.size()){
        ll at = list[i];
        each(i, g[at]) if(!used[i.first]){
            used[i.first] = 1;
            list.push_back(i.first);
        }
    }
    if(all_of(all(list), [](ll at){ return g[at].size() == 2; })){
        ll min = INF;
        each(at, list){
            ans += g[at][0].second;
            chmin(min, g[at][0].second);
        }
        ans -= min;
        return;
    }
    unordered_map<ll, bool> is_circle;
    ll at = start;
    while(!is_circle.count(at)){
        is_circle[at];
        at = g[at][0].first;
    }
    ll circle_sum = 0, circle_cnt = 0;
    while(!is_circle[at]){
        is_circle[at] = 1;
        circle_cnt++;
        circle_sum += g[at][0].second;
        at = g[at][0].first;
    }
    ll mx = 0;
    ll dex = -1;
    unordered_map<ll, ll> dp;
    auto dfs = [&, s = at](ll from, ll at, auto f) -> void {
        each(i, g[at]) if(i.first != from && i.first != s){
            f(at, i.first, f);
            if(!is_circle[i.first]){
                chmax(dp[at], dp[i.first] + i.second);
                if(chmax(mx, dp[at])) dex = at;
            }
        }
    };
    dfs(-1, at, dfs);
    ll cnt = 0;
    rep(circle_cnt){
        ll to = g[at][0].first;
        chmax(cnt, dp[at] + dp[to] + circle_sum - g[at][0].second);
        at = to;
    }
    each(i, g[dex]) if(is_circle[i.first]){
        pll e = i;
        g[dex].erase(find(all(g[dex]), e));
        g[e.first].erase(find(all(g[e.first]), pll{dex, e.second}));
        chmax(cnt, Diameter(dex));
        g[dex].insert(g[dex].begin(), e);
        g[e.first].insert(g[e.first].begin(), pll{dex, e.second});
    }
    ans += cnt;
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;
    used.resize(n);
    g.resize(n);
    rep(n){
        ll a, b;
        cin >> a >> b;
        a--;
        g[i].emplace_back(a, b);
    }
    rep(n) g[g[i][0].first].emplace_back(i, g[i][0].second);
    rep(n) solve(i);
    cout << ans << endl;
}

Compilation message (stderr)

islands.cpp: In function 'void solve(ll)':
islands.cpp:7:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep1(a) for(ll i = 0; i < a; i++)
                                 ^
islands.cpp:6:28: note: in expansion of macro 'rep1'
 #define name3(a,b,c,d,...) d
                            ^
islands.cpp:9:18: note: in expansion of macro 'name3'
 #define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
                  ^~~~~
islands.cpp:53:5: note: in expansion of macro 'rep'
     rep(list.size()){
     ^~~

• Subtask 1: 33 / 33
• Subtask 2: 0 / 3
• Subtask 3: 4 / 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