oj.uz

Submission #53712

# Submission time Handle Problem Language Result Execution time Memory
53712 2018-07-01T05:49:14 Z 강한남자킹현수(#2036) Islands (IOI08_islands) C++11
16 / 100
 860 ms 248996 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
#define X first
#define Y second

const int N = 1000005;
const ll INF = ll(1e18);

vector<pil> e[N];

int n, v[N], o[N], c;
vector<int> w;
vector<ll> d;
ll a[2 * N], b[2 * N], r;

int f(int x, int p){
    //printf("// %d\n", x);
    if(v[x]){
        if(c == -1) return 0;
        //puts("-");
        c = x;
        return 1;
    }
    v[x] = 1;
    int r = 0;
    for(pil i : e[x]){
        if(i.X == p) continue;
        //printf("%d -> %d\n", x, i.X);
        if(f(i.X, x)){
            w.push_back(x);
            d.push_back(i.Y);
            o[x] = 1;
            if(x != c) r = 1;
            else c = -1;
        }
    }
    //printf("%d : %d\n", x, r);
    return r;
}

ll g(int x, int p){
    ll r = 0;
    for(pil i : e[x]){
        if(o[i.X] || i.X == p) continue;
        r = max(r, g(i.X, x) + i.Y);
    }
    return r;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        int x; ll y;
        scanf("%d%lld", &x, &y);
        e[i].push_back({x, y});
        e[x].push_back({i, y});
    }
    for(int i = 1; i <= n; i++){
        if(v[i]) continue;
        w.clear();
        d.clear();
        c = 0;
        f(i, 0);
        int s = w.size();
        //for(int j = 0; j < s; j++) printf("%d %lld\n", w[j], d[j]);
        for(int j = 0; j < s; j++){
            a[j] = a[j + s] = g(w[j], 0);
            b[j] = d[j] + (j ? b[j - 1] : 0);
        }
        for(int j = 0; j < s; j++) b[j + s] = b[j + s - 1] + d[j];
        //for(int j = 0; j < 2 * s; j++) printf("ab %lld %lld\n", a[j], b[j]);
        ll t = 0;
        priority_queue<pli> lq, rq;
        for(int j = 1; j < s; j++) rq.push({a[j] + b[j], j});
        for(int j = 0, k = 0; j < s; j++){
            //printf("jk %d %d\n", j, k);
            while(!lq.empty() && lq.top().Y <= j) lq.pop();
            //puts("#");
            while(k < j + s && b[k] - b[j] < b[j + s] - b[k]) k++;
            //puts("##");
            while(!rq.empty() && rq.top().Y < k){
                int x = rq.top().Y;
                lq.push({a[x] - b[x], x});
                rq.pop();
            }
            //puts("###");
            t = max(t, max((lq.empty() ? -INF : lq.top().X) + b[j + s],
                           (rq.empty() ? -INF : rq.top().X) - b[j]) + a[j]);
            //puts("######");
            rq.push({a[j + s] + b[j + s], j + s});
            //puts("####");
        }
        r += t;
    }
    printf("%lld\n", r);
}

Compilation message

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

Subtask #1
6.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 23928 KB Output isn't correct
2 Incorrect 21 ms 23980 KB Output isn't correct
3 Correct 25 ms 23980 KB Output is correct
4 Incorrect 22 ms 24032 KB Output isn't correct
5 Correct 21 ms 24032 KB Output is correct
6 Incorrect 25 ms 24032 KB Output isn't correct
7 Incorrect 24 ms 24096 KB Output isn't correct
8 Incorrect 24 ms 24096 KB Output isn't correct
9 Incorrect 21 ms 24144 KB Output isn't correct
10 Incorrect 23 ms 24144 KB Output isn't correct
11 Incorrect 25 ms 24144 KB Output isn't correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24164 KB Output is correct
2 Incorrect 25 ms 24164 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 24292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 25532 KB Output is correct
2 Correct 60 ms 29032 KB Output is correct
3 Incorrect 36 ms 29032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 31204 KB Output is correct
2 Correct 79 ms 34012 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 39780 KB Output is correct
2 Incorrect 237 ms 51844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 51844 KB Output is correct
2 Correct 317 ms 89904 KB Output is correct
3 Incorrect 639 ms 112376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 545 ms 112376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 245960 KB Output is correct
2 Correct 568 ms 245960 KB Output is correct
3 Correct 860 ms 248996 KB Output is correct
4 Incorrect 629 ms 248996 KB Output isn't correct
5 Halted 0 ms 0 KB -