답안 #219629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219629 2020-04-05T20:33:03 Z tatyam Islands (IOI08_islands) C++17
70 / 100
1255 ms 131076 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 0x1fffffffffffffff;
#define overload3(a,b,c,d,...) d
#define all(a) begin(a), end(a)
#define rep1(n) for(int i = 0; i < n; i++)
#define rep2(i,n) for(int i = 0; i < n; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : 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; }



struct SlidMax{
    deque<pll> q;
    ll low = 0, high = 0;
    ll pop(){
        ll ans = q[0].first;
        if(q.front().second == low++) q.pop_front();
        return ans;
    }
    void push(ll x){
        while(q.size() && q.back().first <= x) q.pop_back();
        q.emplace_back(x, high++);
    }
};
ll Diameter(const vector<vector<pll>>& g){
    ll n = g.size();
    vector<ll> cost(n, INF);
    vector<bool> used(n);
    queue<ll> q;
    q.push(0);
    cost[0] = 0;
    while(q.size()){
        ll at = q.front();
        q.pop();
        if(used[at]) continue;
        used[at] = 1;
        each(i, g[at]) if(chmin(cost[i.first], cost[at] + i.second)) q.push(i.first);
    }
    ll d = max_element(all(cost)) - cost.begin();
    cost.assign(n, INF);
    used.assign(n, 0);
    q.push(d);
    cost[d] = 0;
    while(q.size()){
        ll at = q.front();
        q.pop();
        if(used[at]) continue;
        used[at] = 1;
        each(i, g[at]) if(chmin(cost[i.first], cost[at] + i.second)) q.push(i.first);
    }
    return *max_element(all(cost));
}
ll solve(const vector<vector<pll>>& g){
    ll n = g.size();
    ll at = 0;
    vector<bool> circle(n);
    rep(n) at = g[at][0].first;
    rep(n){
        at = g[at][0].first;
        circle[at] = 1;
    }
    vector<ll> d(n);
    auto dfs = [&](ll from, ll at, const auto& f) -> void {
        rep(i, 1, g[at].size()){
            ll to = g[at][i].first;
            if(to != from && !circle[to]){
                f(at, to, f);
                chmax(d[at], d[to] + g[at][i].second);
            }
        }
    };
    rep(n) if(circle[i]) dfs(-1, i, dfs);
    ll ans = Diameter(g);
    ll circle_size = accumulate(all(circle), 0);
    vector<ll> len(circle_size * 2 + 1);
    rep(circle_size * 2){
        ll to = g[at][0].first;
        len[i + 1] = len[i] + g[at][0].second;
        at = to;
    }
    SlidMax mx;
    rep(circle_size - 1){
        at = g[at][0].first;
        mx.push(len[i + 1] + d[at]);
    }
    at = g[at][0].first;
    rep(circle_size){
        chmax(ans, mx.pop() - len[i] + d[at]);
        mx.push(len[circle_size + i] + d[at]);
        at = g[at][0].first;
    }
    return ans;
}
int main(){
    ll n;
    cin >> n;
    vector<vector<pll>> G(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);
    vector<ll> idx(n, -1);
    ll ans = 0;
    rep(n) if(idx[i] == -1){
        vector<ll> vertex;
        auto cc = [&](ll at, const auto& f) -> void {
            idx[at] = vertex.size();
            vertex.push_back(at);
            each(i, G[at]) if(idx[i.first] == -1) f(i.first, f);
        };
        cc(i, cc);
        ll n = vertex.size();
        vector<vector<pll>> g(n);
        rep(n){
            auto& edge = G[vertex[i]][0];
            g[i].emplace_back(idx[edge.first], edge.second);
        }
        rep(n){
            auto& edge = G[vertex[i]][0];
            g[idx[edge.first]].emplace_back(i, edge.second);
        }
        ans += solve(g);
    }
    cout << ans << endl;
}

Compilation message

islands.cpp: In instantiation of 'solve(const std::vector<std::vector<std::pair<long long int, long long int> > >&)::<lambda(ll, ll, const auto:1&)> [with auto:1 = solve(const std::vector<std::vector<std::pair<long long int, long long int> > >&)::<lambda(ll, ll, const auto:1&)>; ll = long long int]':
islands.cpp:78:40:   required from here
islands.cpp:10:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep3(i,a,b) for(int i = a; i < b; i++)
                                      ^
islands.cpp:6:32: note: in expansion of macro 'rep3'
 #define overload3(a,b,c,d,...) d
                                ^
islands.cpp:11:18: note: in expansion of macro 'overload3'
 #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
                  ^~~~~~~~~
islands.cpp:70:9: note: in expansion of macro 'rep'
         rep(i, 1, g[at].size()){
         ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 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 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 10 ms 1280 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2296 KB Output is correct
2 Correct 55 ms 8440 KB Output is correct
3 Correct 36 ms 4600 KB Output is correct
4 Correct 19 ms 2432 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 11760 KB Output is correct
2 Correct 128 ms 13276 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 304 ms 39656 KB Output is correct
2 Correct 285 ms 36020 KB Output is correct
3 Correct 371 ms 60872 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 39152 KB Output is correct
2 Correct 680 ms 115040 KB Output is correct
3 Correct 697 ms 96036 KB Output is correct
4 Runtime error 850 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1171 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1255 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -