oj.uz

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;
}

Subtask #1
12.0 / 33.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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 23916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 23916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 24556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 26340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 33004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 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 -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 70772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 63980 KB Time limit exceeded
2 Halted 0 ms 0 KB -