oj.uz

답안 #53762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53762 2018-07-01T06:59:00 Z 강한남자킹현수(#2036) Islands (IOI08_islands) C++11
100 / 100
 1678 ms 233344 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

vector<pili> e[N];

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

void f(int x, int y){
    if(q[x]){
        p[c] = -1;
        for(int i = c - 1; p[i + 1] != x; i--){
            w.push_back(p[i]);
            d.push_back(u[i]);
            o[p[i]] = 1;
        }
        return;
    }
    if(v[x]) return;
    v[x] = 1;
    int r = 0;
    for(pili i : e[x]){
        if(i.Y == y) continue;
        q[x] = 1;
        p[c] = x;
        u[c] = i.X.Y;
        c++;
        f(i.X.X, i.Y);
        q[x] = 0;
        c--;
    }
}

ll g(int x, int p, ll &t){
    pll r = {0, 0};
    for(pili i : e[x]){
        if(o[i.X.X] || i.X.X == p) continue;
        ll z = g(i.X.X, x, t) + i.X.Y;
        if(z >= r.X){ r.Y = r.X; r.X = z; }
        else if(z > r.Y){ r.Y = z; }
    }
    t = max(t, r.X + r.Y);
    return r.X;
}

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(pili(pil(x, y), i));
        e[x].push_back(pili(pil(i, y), i));
    }
    for(int i = 1; i <= n; i++){
        if(v[i]) continue;
        w.clear();
        d.clear();
        f(i, 0);
        int s = w.size();
        //for(int j = 0; j < s; j++) printf("aa %d %lld\n", w[j], d[j]);
        ll t = 0;
        for(int j = 0; j < s; j++){
            a[j] = a[j + s] = g(w[j], 0, t);
            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("bb %lld %lld\n", a[j], b[j]);
        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++){
            while(k < j + s && b[k] - b[j] < b[j + s] - b[k]) k++;
            //printf("jk %d %d\n", j, k);
            while(!rq.empty() && rq.top().Y < k){
                int x = rq.top().Y;
                //printf("rq -> lq %lld %d\n", a[x] - b[x], x);
                lq.push({a[x] - b[x], x});
                rq.pop();
            }
            while(!lq.empty() && lq.top().Y <= j) lq.pop();
            //if(!lq.empty()) printf("lq %lld\n", lq.top().X + b[j + s]);
            //if(!rq.empty()) printf("rq %lld\n", rq.top().X - b[j]);
            t = max(t, max((lq.empty() ? -INF : lq.top().X) + b[j + s],
                           (rq.empty() ? -INF : rq.top().X) - b[j]) + a[j]);
            rq.push({a[j + s] + b[j + s], j + s});
            //printf("rq push %lld %d\n", a[j + s] + b[j + s], j + s);
        }
        //printf("t %lld\n", t);
        r += t;
    }
    printf("%lld\n", r);
}

Compilation message

islands.cpp: In function 'void f(int, int)':
islands.cpp:34:9: warning: unused variable 'r' [-Wunused-variable]
     int r = 0;
         ^
islands.cpp: In function 'int main()':
islands.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
islands.cpp:63: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
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 21 ms 23912 KB Output is correct
3 Correct 22 ms 23980 KB Output is correct
4 Correct 21 ms 23980 KB Output is correct
5 Correct 23 ms 23984 KB Output is correct
6 Correct 23 ms 24040 KB Output is correct
7 Correct 23 ms 24204 KB Output is correct
8 Correct 23 ms 24204 KB Output is correct
9 Correct 23 ms 24204 KB Output is correct
10 Correct 21 ms 24204 KB Output is correct
11 Correct 24 ms 24204 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 24300 KB Output is correct
2 Correct 25 ms 24792 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 25724 KB Output is correct
2 Correct 52 ms 29180 KB Output is correct
3 Correct 38 ms 29180 KB Output is correct
4 Correct 38 ms 29180 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 31348 KB Output is correct
2 Correct 79 ms 35192 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 42584 KB Output is correct
2 Correct 257 ms 53584 KB Output is correct
3 Correct 202 ms 67928 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 67928 KB Output is correct
2 Correct 324 ms 92132 KB Output is correct
3 Correct 502 ms 114828 KB Output is correct
4 Correct 454 ms 131528 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 428 ms 131528 KB Output is correct
2 Correct 1349 ms 165852 KB Output is correct
3 Correct 549 ms 165852 KB Output is correct
4 Correct 722 ms 165852 KB Output is correct
5 Correct 646 ms 165852 KB Output is correct
6 Correct 1629 ms 165852 KB Output is correct
7 Correct 739 ms 197964 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 618 ms 197964 KB Output is correct
2 Correct 574 ms 197964 KB Output is correct
3 Correct 869 ms 233344 KB Output is correct
4 Correct 796 ms 233344 KB Output is correct
5 Correct 631 ms 233344 KB Output is correct
6 Correct 660 ms 233344 KB Output is correct
7 Correct 1678 ms 233344 KB Output is correct