oj.uz

Submission #92268

# Submission time Handle Problem Language Result Execution time Memory
92268 2019-01-02T11:01:41 Z Retro3014 Islands (IOI08_islands) C++17
90 / 100
 1533 ms 132096 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;
#define MAX_N 1000000
typedef long long ll;

int N;
struct S{
    int idx;
    ll data;
};
vector<S> gp[MAX_N+1];
int a, b;

struct C{
    ll a, b;
};
deque<C> cycle;
bool vst[MAX_N+1];

int num[MAX_N+1];
ll len[MAX_N+1];
deque<int> leaf;
ll m[MAX_N+1][3];
ll ans=0;
vector<S> gp2;

int main(){
    scanf("%d", &N);
    for(int i=1; i<=N; i++){
        scanf("%d%d", &a, &b);
        gp[i].push_back((S){a, (ll)b}); num[i]++;
        gp[a].push_back((S){i, (ll)b}); num[a]++;
    }
    for(int i=1; i<=N; i++){
        if(num[i]==1){
            leaf.push_back(i);
        }
    }
    while(!leaf.empty()){
        int now=leaf.front(); leaf.pop_front();
        vst[now]=true;
        m[now][0]=max(m[now][0], m[now][1]+m[now][2]);
        for(int i=0; i<gp[now].size(); i++){
            if(!vst[gp[now][i].idx]){
                len[gp[now][i].idx]=max(len[gp[now][i].idx], len[now]+gp[now][i].data);
                m[gp[now][i].idx][0]=max(m[gp[now][i].idx][0], m[now][0]);
                if(len[now]+gp[now][i].data>m[gp[now][i].idx][1]){
                    m[gp[now][i].idx][2]=m[gp[now][i].idx][1];
                    m[gp[now][i].idx][1]=len[now]+gp[now][i].data;
                }else if(len[now]+gp[now][i].data>m[gp[now][i].idx][2]){
                    m[gp[now][i].idx][2]=len[now]+gp[now][i].data;
                }
                num[gp[now][i].idx]--;
                if(num[gp[now][i].idx]==1){
                    leaf.push_back(gp[now][i].idx);
                }
            }
        }
    }
    ll ans2=0;
    ll sum=0, m1, m2;
    int t;
    for(int i=1; i<=N; i++){
        if(!vst[i]){
            for(int j=0; j<gp[i].size(); j++){
                if(!vst[gp[i][j].idx]){
                    gp2.push_back(gp[i][j]);
                }
            }
            while(!gp[i].empty())    gp[i].pop_back();
            while(!gp2.empty()){
                gp[i].push_back(gp2.back()); gp2.pop_back();
            }
        }
    }
    for(int i=1; i<=N; i++){
        t=i;
        if(!vst[i]){
            cycle.push_front({gp[i][1].idx, gp[i][1].data});
            while(1){
                vst[t]=true;
                if(vst[gp[t][0].idx]){
                    if(vst[gp[t][1].idx]){
                        break;
                    }
                    cycle.push_front({t, gp[t][1].data});
                    t=gp[t][1].idx;
                }else{
                    cycle.push_front({t, gp[t][0].data});
                    t=gp[t][0].idx;
                }
            }
            ans2=0; sum=0;
            for(int j=0; j<cycle.size(); j++){
                sum+=cycle[j].b;
                ans2=max(ans2, max(m[cycle[j].a][0], m[cycle[j].a][1]+m[cycle[j].a][2]));
            }
            /*while(!c.empty()){
                S now = c.back(); c.pop_back();
                ans2=max(ans2, max(m[now.idx][0], m[now.idx][1]+m[now.idx][2]));
                sum+=now.data;
                cycle.push_back({now.data, len[now.idx]});
            }*/
            m1 = m2 = 0;
            while(!cycle.empty()){
                C now = cycle.back(); cycle.pop_back();
                ans2=max(ans2, max(len[now.a], max(m1+len[now.a], m2+len[now.a])));
                m1=max(m1+now.b, now.b+len[now.a]);
                m2=max(m2-now.b, sum-now.b+len[now.a]);
            }
            ans+=ans2;
        }
    }
    printf("%lld", ans);
    return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<gp[now].size(); i++){
                      ~^~~~~~~~~~~~~~~
islands.cpp:69:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<gp[i].size(); j++){
                          ~^~~~~~~~~~~~~
islands.cpp:98:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<cycle.size(); j++){
                          ~^~~~~~~~~~~~~
islands.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
islands.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23928 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct
3 Correct 19 ms 23800 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 22 ms 23800 KB Output is correct
7 Correct 22 ms 23800 KB Output is correct
8 Correct 22 ms 23876 KB Output is correct
9 Correct 21 ms 23800 KB Output is correct
10 Correct 22 ms 23932 KB Output is correct
11 Correct 23 ms 23772 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 23936 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 25 ms 24156 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 25208 KB Output is correct
2 Correct 43 ms 27260 KB Output is correct
3 Correct 36 ms 25820 KB Output is correct
4 Correct 28 ms 24696 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 28552 KB Output is correct
2 Correct 64 ms 31940 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 41592 KB Output is correct
2 Correct 119 ms 39884 KB Output is correct
3 Correct 146 ms 48752 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 56408 KB Output is correct
2 Correct 277 ms 71408 KB Output is correct
3 Correct 272 ms 62200 KB Output is correct
4 Correct 334 ms 87012 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 103468 KB Output is correct
2 Correct 1016 ms 125096 KB Output is correct
3 Correct 438 ms 103800 KB Output is correct
4 Correct 517 ms 129832 KB Output is correct
5 Correct 492 ms 129704 KB Output is correct
6 Correct 1421 ms 126244 KB Output is correct
7 Runtime error 541 ms 132096 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 107640 KB Output is correct
2 Correct 447 ms 107592 KB Output is correct
3 Correct 468 ms 92468 KB Output is correct
4 Correct 492 ms 76512 KB Output is correct
5 Correct 497 ms 118036 KB Output is correct
6 Correct 563 ms 111836 KB Output is correct
7 Correct 1533 ms 112816 KB Output is correct