Submission #337334

# Submission time Handle Problem Language Result Execution time Memory
337334 2020-12-19T19:38:10 Z arbor Islands (IOI08_islands) C++17
12 / 100
2000 ms 70772 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;
}
# Verdict Execution time Memory Grader output
1 Correct 18 ms 23820 KB Output is correct
2 Execution timed out 2081 ms 23916 KB Time limit exceeded
3 Correct 16 ms 23916 KB Output is correct
4 Execution timed out 2082 ms 23788 KB Time limit exceeded
5 Correct 16 ms 23788 KB Output is correct
6 Execution timed out 2097 ms 23788 KB Time limit exceeded
7 Execution timed out 2078 ms 23788 KB Time limit exceeded
8 Execution timed out 2076 ms 23788 KB Time limit exceeded
9 Execution timed out 2067 ms 23788 KB Time limit exceeded
10 Execution timed out 2076 ms 23788 KB Time limit exceeded
11 Correct 18 ms 24044 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 23916 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 23916 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 24556 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 26340 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 33004 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 148 ms 45188 KB Output is correct
2 Execution timed out 2073 ms 47140 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 70772 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 63980 KB Time limit exceeded
2 Halted 0 ms 0 KB -