제출 #122215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122215		thebes	Islands (IOI08_islands)	C++14	51 / 100	669 ms	131072 KiB

islands

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10