Submission #219651

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219651	2020-04-05T21:55:44 Z	tatyam	Islands (IOI08_islands)	C++17	Compilation error	0 ms	0 KB

islands

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
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; }
 
 
 template<class F> class [[nodiscard]] FixPoint : private F {
 public:
    explicit constexpr FixPoint(F&& f) noexcept : F(std::forward<F>(f)){}
    template<typename... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept(noexcept(F::operator()(std::declval<FixPoint>(), std::declval<Args>()...))){
     return F::operator()(*this, std::forward<Args>(args)...);
   }
 };
struct SlidMax{
    deque<pair<ll, int>> q; // 8MB?
    int 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<pii>>& g){
    int n = g.size();
    vector<ll> cost(n, INF); // 8MB
    vector<bool> used(n); // 1MB
    queue<int> q; // 6MB
    q.push(0);
    cost[0] = 0;
    while(q.size()){
        int at = q.front();
        q.pop();
        if(used[at]) continue;
        used[at] = 1;
        each(i, g[at]) if(cost[i.first] == INF){
            cost[i.first] = cost[at] + i.second;
            q.push(i.first);
        }
    }
    int d = max_element(all(cost)) - cost.begin();
    cost.assign(n, INF);
    used.assign(n, 0);
    q.push(d);
    cost[d] = 0;
    while(q.size()){
        int at = q.front();
        q.pop();
        if(used[at]) continue;
        used[at] = 1;
        each(i, g[at]) if(cost[i.first] == INF){
            cost[i.first] = cost[at] + i.second;
            q.push(i.first);
        }
    }
    return *max_element(all(cost));
}
ll solve(const vector<vector<pii>>& g){
    int n = g.size();
    int at = 0;
    vector<bool> circle(n); // 1MB
    rep(n) at = g[at][0].first;
    rep(n){
        at = g[at][0].first;
        circle[at] = 1;
    }
    vector<ll> d(n); // 8MB
    rep(n) if(circle[i]) FixPoint{[&circle, &g, &d](const auto& f, int from, int at) -> void { // 20MB
            rep(i, 1, g[at].size()){
                const int to = g[at][i].first;
                if(to != from && !circle[to]){
                    f(at, to);
                    chmax(d[at], d[to] + g[at][i].second);
                }
            }
        }}(-1, i);
    ll ans = Diameter(g);
    int circle_size = accumulate(all(circle), 0);
    vector<ll> len(circle_size * 2 + 1); // 16MB
    rep(circle_size * 2){
        int 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(){
    int n;
    cin >> n;
    vector<vector<pii>> G(n); // 24MB
    rep(n){
        int 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<int> idx(n, -1); // 4MB
    ll ans = 0;
    rep(n) if(idx[i] == -1){
        vector<int> vertex = {i};
        idx[i] = 0;
        for(int i = 0; i < vertex.size(); i++){
            for(auto& [to, d] : G[vertex[i]]){
                if(idx[to] == -1){
                    idx[to] = vertex.size();
                    vertex.push_back(to);
                }
            }
        }
        int n = vertex.size();
        vector<vector<pii>> g(n);
        rep(n){
            auto& edge = G[vertex[i]][0];
            g[i].emplace_back(idx[edge.first], edge.second);
        }
        each(i, vertex){
            G[i].clear();
            G[i].shrink_to_fit();
        }
        vertex.clear();
        vertex.shrink_to_fit();
        rep(n){
            auto& edge = g[i][0];
            g[edge.first].emplace_back(i, edge.second);
        }
        ans += solve(g);
    }
    cout << ans << endl;
}

Compilation message

islands.cpp: In instantiation of 'constexpr decltype(auto) FixPoint<F>::operator()(Args&& ...) const [with Args = {int, int&}; F = solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)>]':
islands.cpp:91:17:   required from here
islands.cpp:22:121: error: cannot call member function 'solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> [with auto:1 = FixPoint<solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> >]' without object
     template<typename... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept(noexcept(F::operator()(std::declval<FixPoint>(), std::declval<Args>()...))){
                                                                                                            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp: In instantiation of 'constexpr decltype(auto) FixPoint<F>::operator()(Args&& ...) const [with Args = {int, int&}; F = solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)>]':
islands.cpp:91:17:   required from here
islands.cpp:22:121: error: cannot call member function 'solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> [with auto:1 = FixPoint<solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> >]' without object
islands.cpp: In instantiation of 'solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> [with auto:1 = FixPoint<solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> >]':
islands.cpp:23:26:   required from 'constexpr decltype(auto) FixPoint<F>::operator()(Args&& ...) const [with Args = {int, int&}; F = solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)>]'
islands.cpp:91:17:   required from here
islands.cpp:11: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:7:32: note: in expansion of macro 'rep3'
 #define overload3(a,b,c,d,...) d
                                ^
islands.cpp:12:18: note: in expansion of macro 'overload3'
 #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
                  ^~~~~~~~~
islands.cpp:84:13: note: in expansion of macro 'rep'
             rep(i, 1, g[at].size()){
             ^~~
islands.cpp: In instantiation of 'constexpr decltype(auto) FixPoint<F>::operator()(Args&& ...) const [with Args = {int&, const int&}; F = solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)>]':
islands.cpp:87:22:   required from 'solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> [with auto:1 = FixPoint<solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> >]'
islands.cpp:23:26:   required from 'constexpr decltype(auto) FixPoint<F>::operator()(Args&& ...) const [with Args = {int, int&}; F = solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)>]'
islands.cpp:91:17:   required from here
islands.cpp:22:121: error: cannot call member function 'solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> [with auto:1 = FixPoint<solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> >]' without object
     template<typename... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept(noexcept(F::operator()(std::declval<FixPoint>(), std::declval<Args>()...))){
                                                                                                            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp: In instantiation of 'constexpr decltype(auto) FixPoint<F>::operator()(Args&& ...) const [with Args = {int&, const int&}; F = solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)>]':
islands.cpp:87:22:   required from 'solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> [with auto:1 = FixPoint<solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> >]'
islands.cpp:23:26:   required from 'constexpr decltype(auto) FixPoint<F>::operator()(Args&& ...) const [with Args = {int, int&}; F = solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)>]'
islands.cpp:91:17:   required from here
islands.cpp:22:121: error: cannot call member function 'solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> [with auto:1 = FixPoint<solve(const std::vector<std::vector<std::pair<int, int> > >&)::<lambda(const auto:1&, int, int)> >]' without object
islands.cpp: In function 'int main()':
islands.cpp:129:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < vertex.size(); i++){
                        ~~^~~~~~~~~~~~~~~
islands.cpp:130:29: warning: unused variable 'd' [-Wunused-variable]
             for(auto& [to, d] : G[vertex[i]]){
                             ^