Submission #59504

#	Time	Username	Problem	Language	Result	Execution time	Memory
59504		TAMREF	Islands (IOI08_islands)	C++11	31 / 100	998 ms	132096 KiB

islands

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

const int mx = 1e6 + 5;

struct Edg{
    int u, v, w;
    inline int oppo(int x){
        return u + v - x;
    }
} E[mx];

vector<int> G[mx];
int vis[mx];
bool dE[mx];
int num_cyc = 1; //greater than 1
int n;


vector<int> cv; //cycle vertex
vector<ll> ce; //cycle edge weight
vector<ll> Vei, Wei;

int dfs(int x, int nume){
    int cyc = 0, tcyc, u;
    vis[x] = 1;
    for(int &e : G[x]){
        if(dE[e]) continue;
        u = E[e].oppo(x);
        if(vis[u]){
            //printf("cycle detected - (%d->%d)\n",x,u);
            cyc = u;
            dE[e] = 1;
            ce.push_back(E[e].w);
        }else{
            dE[e] = 1;
            tcyc = dfs(u,e);
            cyc |= tcyc;
            if(tcyc){
                ce.push_back(E[e].w);
            }
        }
    }
    if(cyc){
        //printf("push %d in cv\n",x);
        cv.push_back(x);
    }
    if(cyc == x){
        //printf("stopping cycle in %d\n",x);
        cyc = 0;
    }
    return cyc;
}

ll dfs_st(int x, int c){ //dfs for each subtrees in cycle
    vis[x] = c;
    int u, w;
    ll ans = 0;
    for(int &e : G[x]){
        u = E[e].oppo(x);
        w = E[e].w;
        if(vis[u] == 1){
            ans = max(ans, dfs_st(u, c) + w);
        }
    }
    return ans;
}

pli dq[2 * mx];
int dq_f, dq_r;

inline void BackInsert(pli p){
    while(dq_f != dq_r && dq[dq_r] <= p) --dq_r;
    dq[dq_r++] = p;
}

inline void OldPop(int k){
    while(dq_f != dq_r && dq[dq_f].second < k) ++dq_f;
}

ll calc(vector<ll>& Vw, vector<ll>& E, vector<ll>& sE){
    dq_f = dq_r = 0;

    int m = E.size();
    ll lsum = E[0];
    ll ret = 0;

    for(int i = 1; i < m; i++){
        BackInsert(pli(Vw[i] + sE[i], i));
        lsum += E[i];
    }
    for(int i = 0; i < m; i++){
        OldPop(i+1);
        ret = max(ret, Vw[i] - sE[i] + dq[dq_f].first);
        BackInsert(pli(Vw[i] + lsum + sE[i], i+m));
    }
    return ret;
}

ll dp_on_cycle(){
    int C = cv.size();
    ll lsum = 0;
    ll ans = 0;
    //give cycle-vertices their own number
    rotate(ce.begin(),ce.begin()+1,ce.end()); //f**k
    for(int i = 0; i < C; i++){
        vis[cv[i]] = ++num_cyc;
        //printf("vertex : %d, clockwise - edge : %d\n",cv[i],ce[i]);
    }
    //clockwise
    for(int i = 0; i < C; i++){
        Vei.push_back( dfs_st(cv[i], vis[cv[i]]) );
        Wei.push_back( lsum );
        lsum += ce[i]; //copy
    }
    ans = max(ans, calc(Vei, ce, Wei));

    //inclockwise - reversing all the vectors
    lsum = 0;
    reverse(cv.begin(),cv.end());
    reverse(Vei.begin(),Vei.end());

    if(C > 2) reverse(ce.begin(), ce.end() - 1);
    else reverse(ce.begin(), ce.end());

    for(int i = 0; i < C; i++){
        //printf("vertex : %d, Inc ew : %d\n",cv[i],ce[i]);
        Wei[i] = lsum;
        lsum += ce[i];
    }

    ans = max(ans, calc(Vei, ce, Wei));

    //printf("dp result : %lld\n",ans);
    return ans;
}

void input(){
    cin >> n;
    cv.reserve(n);
    ce.reserve(n);
    Wei.reserve(n);
    Vei.reserve(n);
    for(int i = 1; i <= n; i++){
        cin >> E[i].v >> E[i].w;
        E[i].u = i;
        G[i].push_back(i);
        G[E[i].v].push_back(i);
    }
}

void debug(){
    FILE *fp = fopen("isl19f.out","rt");
    ll correct;
    fscanf(fp,"%lld",&correct);
    cout << "answer = " << correct << '\n';
}

int main(){
    //freopen("isl19f.in","rt",stdin);
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll ans = 0;
    input();
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            cv.clear();
            ce.clear();
            Wei.clear();
            Vei.clear();
            dfs(i,0);
            ans += dp_on_cycle();
        }
    }
    cout << ans << '\n';
    //debug();
}

Compilation message (stderr)

islands.cpp: In function 'void debug()':
islands.cpp:159:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fp,"%lld",&correct);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 27 / 33
• Subtask 2: 0 / 3
• Subtask 3: 4 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10