oj.uz

Submission #122211

# Submission time Handle Problem Language Result Execution time Memory
122211 2019-06-27T20:44:02 Z thebes Islands (IOI08_islands) C++14
41 / 100
 673 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 1e6+6;
typedef long long ll;
ll dp[MN], N, i, j, x, y, ans, vis[MN], X[MN], L[MN], tmp, r[MN], len[MN], rev[MN], stk[MN];
vector<pair<ll,ll>> adj[MN];
vector<ll> cyc, lol;
stack<int> st;
pair<ll,ll> d;

void dfs(int n){
    vis[n]=1; st.push(n); stk[n]=1;
    for(auto w : adj[n]){
        auto v = w.first;
        if(stk[v]){
            cyc.clear();
            while(st.size()&&st.top()!=v){
                cyc.push_back(st.top());
                st.pop();
            }
            cyc.push_back(st.top());
            st.pop();
        }
        else if(!vis[v]){
            dfs(v);
        }
        break;
    }
    if(st.size()&&st.top()==n) st.pop();
    stk[n]=0;
}

ll dfs1(ll n,ll p){
    ll a=0, b=0; dp[n]=0;
    for(auto v : adj[n]){
        if(make_pair(v.first,n)==d||make_pair(n,v.first)==d||v.first==p||r[v.first]) continue;
        ll dd = dfs1(v.first, n)+v.second;
        dp[n] = max(dp[n], dd);
        if(dd>a) b=a, a=dd;
        else if(dd>b) b=dd;
    }
    tmp = max(tmp, a+b);
    return dp[n];
}

int main(){
    for(scanf("%lld",&N),i=1;i<=N;i++){
        scanf("%lld%lld",&x,&y);
        adj[i].push_back({x,y});
        X[i]=x; L[i]=y;
    }
    for(int v=1;v<=N;v++){
        adj[X[v]].push_back({v,L[v]});
    }
    for(i=1;i<=N;i++){
        if(vis[i]) continue;
        cyc.clear(); dfs(i);
        if(cyc.empty()) continue;
        d = {cyc[0],cyc[1]};
        tmp=0; dfs1(cyc[0], 0);
        for(auto v : cyc) r[v]=1;
        lol.clear();
        ll dist = 0;
        for(auto v : adj[cyc[0]]){
            if(v.first==cyc[1]){
                dist = v.second;
                break;
            }
        }
        for(j=1;j<cyc.size();j++){
            for(auto v : adj[cyc[j]]){
                if(v.first==cyc[(j+1)%cyc.size()]){
                    len[cyc[j]]=v.second;
                    rev[cyc[(j+1)%cyc.size()]]=v.second;
                    break;
                }
            }
            dfs1(cyc[j],0);
            ll heh=lol.size()?lol.back():0LL;
            lol.push_back(max(dp[cyc[j]]+dist,heh));
            dist += len[cyc[j]];
        }
        ll opt = dfs1(cyc[0],0);
        dist = 0;
        for(j=cyc.size()-1;j>=1;j--){
            tmp = max(tmp, lol[j-1]+opt);
            dist += rev[cyc[(j+1)%cyc.size()]];
            opt = max(opt, dist+dp[cyc[j]]);
        }
        ans += tmp;
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=1;j<cyc.size();j++){
                 ~^~~~~~~~~~~
islands.cpp:48:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&N),i=1;i<=N;i++){
         ~~~~~~~~~~~~~~~~^~~~
islands.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 21 ms 23936 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Incorrect 21 ms 23808 KB Output isn't correct
7 Incorrect 21 ms 23936 KB Output isn't correct
8 Correct 24 ms 23944 KB Output is correct
9 Incorrect 22 ms 23808 KB Output isn't correct
10 Correct 23 ms 23968 KB Output is correct
11 Incorrect 22 ms 23936 KB Output isn't correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24064 KB Output is correct
2 Incorrect 23 ms 24048 KB Output isn't correct

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 26092 KB Output is correct
2 Correct 45 ms 30316 KB Output is correct
3 Incorrect 36 ms 26872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 32864 KB Output is correct
2 Correct 75 ms 39068 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 51964 KB Output is correct
2 Correct 153 ms 58260 KB Output is correct
3 Correct 191 ms 75496 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 78672 KB Output is correct
2 Correct 305 ms 113684 KB Output is correct
3 Correct 344 ms 120868 KB Output is correct
4 Runtime error 392 ms 131072 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 Correct 420 ms 125728 KB Output is correct
2 Runtime error 673 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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