Submission #219609

# Submission time Handle Problem Language Result Execution time Memory
219609 2020-04-05T17:58:00 Z tatyam Islands (IOI08_islands) C++17
37 / 100
670 ms 131076 KB
#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

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()){
     ^~~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 10 ms 1408 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 29 ms 2320 KB Output is correct
2 Incorrect 65 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 13256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 45704 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 670 ms 40668 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 474 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -