oj.uz

Submission #122213

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

const int MN = 1e6+6;
typedef long long ll;
short vis[MN], r[MN], stk[MN];
int X[MN], L[MN];
ll dp[MN], N, i, j, x, y, ans, tmp, len[MN], rev[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:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=1;j<cyc.size();j++){
                 ~^~~~~~~~~~~
islands.cpp:50: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:51: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 26 ms 23848 KB Output is correct
2 Correct 24 ms 24064 KB Output is correct
3 Correct 26 ms 23936 KB Output is correct
4 Correct 24 ms 23808 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Incorrect 23 ms 23808 KB Output isn't correct
7 Incorrect 24 ms 23928 KB Output isn't correct
8 Correct 25 ms 24064 KB Output is correct
9 Incorrect 23 ms 23936 KB Output isn't correct
10 Correct 23 ms 23808 KB Output is correct
11 Incorrect 23 ms 23928 KB Output isn't correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 24064 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 25728 KB Output is correct
2 Correct 47 ms 29308 KB Output is correct
3 Incorrect 42 ms 26232 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 59 ms 31328 KB Output is correct
2 Correct 70 ms 35524 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 44796 KB Output is correct
2 Correct 151 ms 50832 KB Output is correct
3 Correct 189 ms 65756 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 63388 KB Output is correct
2 Correct 281 ms 95424 KB Output is correct
3 Correct 326 ms 100744 KB Output is correct
4 Correct 422 ms 131072 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 90832 KB Output is correct
2 Runtime error 701 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 446 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -