oj.uz

Submission #122214

# Submission time Handle Problem Language Result Execution time Memory
122214 2019-06-27T20:51:36 Z thebes Islands (IOI08_islands) C++14
41 / 100
 728 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];
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;
vector<int> X, L;

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(){
    X.resize(MN);
    L.resize(MN);
    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]});
    }
    X.clear();
    L.clear();
    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:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=1;j<cyc.size();j++){
                 ~^~~~~~~~~~~
islands.cpp:52: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:53: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 29 ms 31744 KB Output is correct
2 Correct 28 ms 31736 KB Output is correct
3 Correct 29 ms 31736 KB Output is correct
4 Correct 28 ms 31744 KB Output is correct
5 Correct 29 ms 31744 KB Output is correct
6 Incorrect 29 ms 31744 KB Output isn't correct
7 Incorrect 29 ms 31744 KB Output isn't correct
8 Correct 28 ms 31736 KB Output is correct
9 Incorrect 29 ms 31736 KB Output isn't correct
10 Correct 29 ms 31752 KB Output is correct
11 Incorrect 29 ms 31744 KB Output isn't correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31844 KB Output is correct
2 Incorrect 31 ms 31872 KB Output isn't correct

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 33280 KB Output is correct
2 Correct 53 ms 36648 KB Output is correct
3 Incorrect 43 ms 33556 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 63 ms 38496 KB Output is correct
2 Correct 77 ms 42396 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 50608 KB Output is correct
2 Correct 159 ms 56592 KB Output is correct
3 Correct 191 ms 71412 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 67704 KB Output is correct
2 Correct 303 ms 99136 KB Output is correct
3 Correct 343 ms 103592 KB Output is correct
4 Runtime error 409 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 371 ms 90560 KB Output is correct
2 Runtime error 728 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 450 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -