oj.uz

Submission #122215

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

const int MN = 1e6+6;
typedef long long ll;
bitset<MN> stk;
int vis[MN], r[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});
        vis[i]=x; r[i]=y;
    }
    for(int v=1;v<=N;v++){
        adj[vis[v]].push_back({v,r[v]});
    }
    memset(vis,0,sizeof(vis));
    memset(r,0,sizeof(r));
    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:75: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 28 ms 31608 KB Output is correct
2 Correct 28 ms 31736 KB Output is correct
3 Correct 29 ms 31744 KB Output is correct
4 Correct 28 ms 31576 KB Output is correct
5 Correct 28 ms 31736 KB Output is correct
6 Incorrect 28 ms 31716 KB Output isn't correct
7 Incorrect 29 ms 31616 KB Output isn't correct
8 Correct 29 ms 31872 KB Output is correct
9 Incorrect 30 ms 31608 KB Output isn't correct
10 Correct 29 ms 31744 KB Output is correct
11 Incorrect 29 ms 31608 KB Output isn't correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31744 KB Output is correct
2 Incorrect 30 ms 31832 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 31864 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 33144 KB Output is correct
2 Correct 53 ms 36344 KB Output is correct
3 Incorrect 42 ms 33400 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 64 ms 38100 KB Output is correct
2 Correct 73 ms 41784 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 49536 KB Output is correct
2 Correct 162 ms 55504 KB Output is correct
3 Correct 185 ms 69864 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 65448 KB Output is correct
2 Correct 290 ms 96276 KB Output is correct
3 Correct 328 ms 100260 KB Output is correct
4 Correct 428 ms 131072 KB Output is correct

Subtask #8
0 / 10.0

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