oj.uz

답안 #92228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92228 2019-01-02T06:56:02 Z Retro3014 Islands (IOI08_islands) C++17
6 / 100
 470 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[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

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.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 23800 KB Output isn't correct
2 Runtime error 193 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Incorrect 22 ms 23928 KB Output isn't correct
4 Runtime error 196 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Correct 22 ms 23800 KB Output is correct
6 Runtime error 189 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 190 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Incorrect 22 ms 23800 KB Output isn't correct
9 Runtime error 192 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 203 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Correct 21 ms 23788 KB Output is correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 23928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 189 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 25592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 31604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 141 ms 44744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 201 ms 62208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 454 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 470 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -