Submission #92228

#	Time	Username	Problem	Language	Result	Execution time	Memory
92228		Retro3014	Islands (IOI08_islands)	C++17	6 / 100	470 ms	132096 KiB

islands

#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[x].idx==0){
                    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(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 (stderr)

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: 6 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10