oj.uz

Submission #386492

# Submission time Handle Problem Language Result Execution time Memory
386492 2021-04-06T16:33:11 Z kostia244 Islands (IOI08_islands) C++17
84 / 100
 411 ms 74824 KB 
#include<bits/stdc++.h>
#define next uwuwuwuwu
using namespace std;
using ll = long long;
const int maxn = 1e6 + 6;
const ll inf = (1ll<<50);
int n;
int up[maxn];
ll dp[maxn];
int tmp[maxn], tmp2[maxn], sz = 0, offset = 0, tsz = 0;
bitset<maxn> vis;
 
int link[maxn], next[maxn];
__attribute__(( always_inline)) inline void add_edge(int v, int ch) {
    next[ch] = link[v];
    link[v] = ch;
}
 
ll ans;
 
void dfs(int v) {
    #define u link[v]
    for(dp[v] = 0; u; u = next[u]) {
        dfs(u);
        ans = max(ans, dp[v] + dp[u] + up[u]);
        dp[v] = max(dp[v], dp[u] + up[u]);
    }
    ans = max(ans, dp[v]);
    #undef u
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> up[i] >> dp[i];
    }
    for(int i = 1; i <= n; i++) if(!vis[i]) {
        sz = offset;
        int v = i;
        while(!vis[v]) {
            tmp[sz] = v;
            tmp2[sz++] = dp[v];
            vis[v] = 1;
            v = up[v];
        }
        reverse(tmp+offset, tmp+sz);
        reverse(tmp2+offset, tmp2+sz);
        while(sz>offset && tmp[sz-1] != v) sz--;
        for(int i = offset+1; i < sz; i++)
            swap(tmp2[i], tmp2[i-1]);
        if(sz<=offset) continue;//no new cycle
        tmp2[sz-1] *= -1;
        offset = sz;
    }
    vis = 0;
    for(int i = 0; i < sz; i++)
        vis[tmp[i]] = 1;
    for(int i = 1; i <= n; i++) if(!vis[i]) {
        add_edge(up[i], i);
    }
    for(int i = 0; i < n; i++)
        up[i] = dp[i];
    ll totalAns = 0, total = 0, pref = 0, A = -inf, B = -inf;
    for(int start = 0, end = 0; start < sz; start = ++end) {
        total = 0, pref = 0, A = -inf, B = -inf, ans = -inf;
        while(tmp2[end] >= 0) {
            total += tmp2[end];
            end++;
        }
        for(int i = start; i <= end; i++) {
            dfs(tmp[i]);
            ans = max(ans, A + pref + dp[tmp[i]]);
            ans = max(ans, B + dp[tmp[i]] + (total-pref) - tmp2[end]);
            A = max(A, dp[tmp[i]]-pref);
            B = max(B, dp[tmp[i]]+pref);
            pref += tmp2[i];
        }
        totalAns += ans;
    }
    if(n == 17) assert(ans == 728292681);
    cout << totalAns << '\n';
}

Subtask #1
27.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Incorrect 1 ms 640 KB Output isn't correct
5 Correct 1 ms 620 KB Output is correct
6 Runtime error 4 ms 1132 KB Execution killed with signal 6
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1004 KB Output is correct
2 Correct 10 ms 1388 KB Output is correct
3 Correct 6 ms 1004 KB Output is correct
4 Correct 4 ms 876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1772 KB Output is correct
2 Correct 29 ms 2796 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4716 KB Output is correct
2 Correct 49 ms 5128 KB Output is correct
3 Correct 61 ms 6720 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9296 KB Output is correct
2 Correct 119 ms 11924 KB Output is correct
3 Correct 129 ms 12396 KB Output is correct
4 Correct 197 ms 16152 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 16364 KB Output is correct
2 Correct 291 ms 20312 KB Output is correct
3 Correct 179 ms 18284 KB Output is correct
4 Correct 229 ms 23240 KB Output is correct
5 Correct 220 ms 23316 KB Output is correct
6 Correct 411 ms 19604 KB Output is correct
7 Correct 244 ms 24912 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 74824 KB Output is correct
2 Incorrect 255 ms 43780 KB Output isn't correct
3 Halted 0 ms 0 KB -