oj.uz

Submission #92231

# Submission time Handle Problem Language Result Execution time Memory
92231 2019-01-02T07:03:53 Z Retro3014 Islands (IOI08_islands) C++17
54 / 100
 506 ms 132096 KB 
#include <iostream>
#include <algorithm>
#include <vector>
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;
};
S from[MAX_N+1];
vector<S> c;
vector<C> cycle;
bool vst[MAX_N+1];
bool isc[MAX_N+1];

void dfs(int x){
    vst[x]=true;
    for(int i=0; i<gp[x].size(); i++){
        if(vst[gp[x][i].idx]){
            if(gp[x][i].idx!=from[x].idx && !isc[x]){
                if(from[gp[x][i].idx].idx==x){
                    c.push_back({gp[x][i].idx, gp[x][i].data});
                    isc[gp[x][i].idx]=true;
                    c.push_back({x, from[gp[x][i].idx].data});
                    isc[x]=true;
                }else{
                    int t=x;
                    c.push_back({gp[x][i].idx, gp[x][i].data});
                    isc[gp[x][i].idx]=true;
                    while(t!=gp[x][i].idx){
                        c.push_back((S){t, from[t].data});
                        isc[t]=true;
                        t=from[t].idx;
                    }
                }
            }
        }else{
            from[gp[x][i].idx].idx=x;
            from[gp[x][i].idx].data=gp[x][i].data;
            dfs(gp[x][i].idx);
        }
    }
}

bool vstc[MAX_N+1];
ll len[MAX_N+1];

ll dfsc(int x){
    vstc[x]=true;
    len[x]=0;
    ll m1=0, m2=0, m=0, ret=0;
    for(int i=0; i<gp[x].size(); i++){
        if(!isc[gp[x][i].idx] && !vstc[gp[x][i].idx]){
            ret=max(ret, dfsc(gp[x][i].idx));
            m=len[gp[x][i].idx];
            if(m>m1){
                m2=m1; m1=m;
            }else if(m>m2)  m2=m;
            len[x]=max(len[x], len[gp[x][i].idx]+gp[x][i].data);
        }
    }
    return max(ret, m1+m2);
}

ll ans=0;

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});
        gp[a].push_back((S){i, (ll)b});
    }
    for(int i=1; i<=N; i++){
        if(!vst[i]){
            dfs(i);
            ll ans2=0;
            ll sum=0;
            while(!c.empty()){
                S now = c.back(); c.pop_back();
                ans2=max(ans2, dfsc(now.idx));
                sum+=now.data;
                cycle.push_back({now.data, len[now.idx]});
            }
            ll m1=0, m2=0;
            while(!cycle.empty()){
                C now = cycle.back(); cycle.pop_back();
                ans2=max(ans2, max(m1+now.b, m2+now.b));
                m1=max(m1+now.a, now.a+now.b);
                m2=max(m2-now.a, sum-now.a+now.b);
            }
            ans+=ans2;
        }
    }
    printf("%lld", ans);
    return 0;
}

Compilation message

islands.cpp: In function 'void dfs(int)':
islands.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gp[x].size(); i++){
                  ~^~~~~~~~~~~~~
islands.cpp: In function 'll dfsc(int)':
islands.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gp[x].size(); i++){
                  ~^~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
islands.cpp:79: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
27.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23876 KB Output is correct
2 Incorrect 22 ms 23928 KB Output isn't correct
3 Correct 22 ms 23928 KB Output is correct
4 Correct 22 ms 23928 KB Output is correct
5 Correct 22 ms 23800 KB Output is correct
6 Correct 22 ms 23800 KB Output is correct
7 Correct 22 ms 23896 KB Output is correct
8 Correct 22 ms 23844 KB Output is correct
9 Correct 22 ms 23800 KB Output is correct
10 Incorrect 22 ms 23800 KB Output isn't correct
11 Correct 20 ms 23800 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24016 KB Output is correct
2 Correct 23 ms 23956 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 25436 KB Output is correct
2 Correct 44 ms 29048 KB Output is correct
3 Correct 35 ms 25848 KB Output is correct
4 Incorrect 29 ms 24736 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31092 KB Output is correct
2 Correct 69 ms 34284 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 42376 KB Output is correct
2 Correct 143 ms 51584 KB Output is correct
3 Correct 172 ms 68700 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 56948 KB Output is correct
2 Correct 271 ms 93060 KB Output is correct
3 Correct 333 ms 104696 KB Output is correct
4 Runtime error 352 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -