oj.uz

Submission #337335

# Submission time Handle Problem Language Result Execution time Memory
337335 2020-12-19T20:06:39 Z arbor Islands (IOI08_islands) C++17
100 / 100
 912 ms 128372 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[2 * MN], mx[MN], mxd, add[2 * 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;
    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
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23916 KB Output is correct
3 Correct 16 ms 23916 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 16 ms 23916 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 16 ms 23936 KB Output is correct
9 Correct 16 ms 24044 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct
11 Correct 17 ms 23916 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 18 ms 24172 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24812 KB Output is correct
2 Correct 32 ms 26860 KB Output is correct
3 Correct 26 ms 25324 KB Output is correct
4 Correct 21 ms 24556 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27372 KB Output is correct
2 Correct 52 ms 31000 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 35552 KB Output is correct
2 Correct 100 ms 39916 KB Output is correct
3 Correct 124 ms 48568 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 45316 KB Output is correct
2 Correct 187 ms 58348 KB Output is correct
3 Correct 202 ms 67368 KB Output is correct
4 Correct 259 ms 86908 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 71880 KB Output is correct
2 Correct 675 ms 111972 KB Output is correct
3 Correct 281 ms 78320 KB Output is correct
4 Correct 365 ms 102508 KB Output is correct
5 Correct 379 ms 101992 KB Output is correct
6 Correct 891 ms 90988 KB Output is correct
7 Correct 399 ms 122620 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 119692 KB Output is correct
2 Correct 429 ms 110956 KB Output is correct
3 Correct 420 ms 128372 KB Output is correct
4 Correct 411 ms 79980 KB Output is correct
5 Correct 381 ms 106496 KB Output is correct
6 Correct 349 ms 92396 KB Output is correct
7 Correct 912 ms 91884 KB Output is correct