oj.uz

답안 #386510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386510 2021-04-06T17:08:54 Z kostia244 Islands (IOI08_islands) C++17
100 / 100
 466 ms 31724 KB 
#include<stdio.h>
#include<cstring>
#include<bitset>
#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;
int STACK[maxn], SZ = 0, v;
__attribute__(( always_inline)) inline void dfs(int V) {
    STACK[SZ++] = V;
    #define u link[v]
    while(SZ) {
        v = STACK[SZ-1];
        if(u < 0) {
            STACK[SZ++] = (u*=-1);
        } else {
            ans = max(ans, dp[v] + dp[u] + up[u]);
            dp[v] = max(dp[v], dp[u] + up[u]);
            u = next[u];
            if(u) STACK[SZ++] = u;
            else SZ--;
        }
    }
    #undef u
}
 
int main() {
    //cin.tie(0)->sync_with_stdio(0);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%lld", &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];
        }
        for(int i = 0; offset+i < sz-i-1; i++) {
            swap(tmp[offset+i], tmp[sz-1-i]);
            swap(tmp2[offset+i], tmp2[sz-1-i]);
        }
        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 i = 0; i <= n; i++) link[i] *= -1;
    memset(dp, 0, sizeof dp);
    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;
    }
    printf("%lld", totalAns);
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
islands.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |         scanf("%d%lld", &up[i], &dp[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8436 KB Output is correct
2 Correct 5 ms 8428 KB Output is correct
3 Correct 5 ms 8428 KB Output is correct
4 Correct 5 ms 8428 KB Output is correct
5 Correct 5 ms 8560 KB Output is correct
6 Correct 5 ms 8428 KB Output is correct
7 Correct 5 ms 8428 KB Output is correct
8 Correct 5 ms 8428 KB Output is correct
9 Correct 5 ms 8428 KB Output is correct
10 Correct 5 ms 8428 KB Output is correct
11 Correct 5 ms 8428 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8428 KB Output is correct
2 Correct 8 ms 8428 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8428 KB Output is correct
2 Correct 6 ms 8428 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8684 KB Output is correct
2 Correct 19 ms 8940 KB Output is correct
3 Correct 11 ms 8684 KB Output is correct
4 Correct 8 ms 8556 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 9196 KB Output is correct
2 Correct 30 ms 9964 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 10860 KB Output is correct
2 Correct 60 ms 11628 KB Output is correct
3 Correct 77 ms 12652 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 14188 KB Output is correct
2 Correct 134 ms 15852 KB Output is correct
3 Correct 141 ms 17536 KB Output is correct
4 Correct 181 ms 18924 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 275 ms 20148 KB Output is correct
2 Correct 341 ms 22124 KB Output is correct
3 Correct 216 ms 20204 KB Output is correct
4 Correct 266 ms 23276 KB Output is correct
5 Correct 259 ms 23276 KB Output is correct
6 Correct 431 ms 19692 KB Output is correct
7 Correct 316 ms 25068 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 31724 KB Output is correct
2 Correct 270 ms 22252 KB Output is correct
3 Correct 274 ms 24172 KB Output is correct
4 Correct 274 ms 24044 KB Output is correct
5 Correct 265 ms 23788 KB Output is correct
6 Correct 262 ms 21100 KB Output is correct
7 Correct 466 ms 19948 KB Output is correct