oj.uz

Submission #337333

# Submission time Handle Problem Language Result Execution time Memory
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]) {
      |               ^

Subtask #1
12.0 / 33.0

# Verdict Execution time Memory 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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 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 2090 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 2095 ms 24684 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 2065 ms 26912 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 2058 ms 35436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory 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 -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 86628 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 2047 ms 79364 KB Time limit exceeded
2 Halted 0 ms 0 KB -