답안 #337333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
337333 2020-12-19T19:37:11 Z arbor Islands (IOI08_islands) C++14
12 / 100
2000 ms 86628 KB
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 1e6 + 5;
int N;
pii nex[MN];
vector<pii> g[MN];
bool vis[MN], done[MN];
ll ps[MN], mx[MN], mxd, add[MN];

void go(int u) {
    done[u] = true;
    for (auto [v, w] : g[u]) {
        if (done[v]) continue;
        go(v);
        mxd = max(mxd, mx[u] + w + mx[v]);
        mx[u] = max(mx[u], w + mx[v]);
    }
}

ll solve(int u) {
    mxd = 0;
    vis[u] = true;
    int sz = 0;
    for (; !vis[u]; u = nex[u].first) vis[u] = true;
    for (int v = nex[u].first; ; v = nex[v].first) {
        done[v] = true;
        if (v == u) break;
    }
    for (int v = nex[u].first; ; v = nex[v].first) {
        sz++;
        go(v);
        add[sz] = mx[v];
        ps[sz + 1] = ps[sz] + nex[v].second;
        if (v == u) break;
    }
    for (int i = sz + 1; i < 2 * sz; i++) {
        add[i] = add[i - sz];
        ps[i + 1] = ps[sz + 1] + ps[i + 1 - sz];
    }
    deque<pair<int, ll>> q;
    for (int i = 1; i < sz * 2; i++) {
        while (!q.empty() && q.front().first <= i - sz) q.pop_front();
        if (!q.empty()) mxd = max(mxd, add[i] + ps[i] + q.front().second);
        ll val = add[i] - ps[i];
        while (!q.empty() && q.back().second <= val) q.pop_back();
        q.emplace_back(i, val);
    }
    return mxd;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int u = 1; u <= N; u++) {
        int v, w; cin >> v >> w;
        nex[u] = {v, w};
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    ll ans = 0;
    for (int i = 1; i <= N; i++) if (!done[i]) ans += solve(i);
    cout << ans << '\n';
    return 0;
}

Compilation message

islands.cpp: In function 'void go(int)':
islands.cpp:15:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for (auto [v, w] : g[u]) {
      |               ^
# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Execution timed out 2071 ms 23916 KB Time limit exceeded
3 Correct 17 ms 23916 KB Output is correct
4 Execution timed out 2084 ms 23788 KB Time limit exceeded
5 Correct 16 ms 23916 KB Output is correct
6 Execution timed out 2093 ms 23788 KB Time limit exceeded
7 Execution timed out 2078 ms 23916 KB Time limit exceeded
8 Execution timed out 2073 ms 23788 KB Time limit exceeded
9 Execution timed out 2091 ms 23916 KB Time limit exceeded
10 Execution timed out 2088 ms 23788 KB Time limit exceeded
11 Correct 16 ms 23916 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2079 ms 23916 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2090 ms 23916 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2095 ms 24684 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 26912 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2058 ms 35436 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 50308 KB Output is correct
2 Execution timed out 2078 ms 52844 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2086 ms 86628 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2047 ms 79364 KB Time limit exceeded
2 Halted 0 ms 0 KB -