답안 #53888 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53888	2018-07-01T14:21:21 Z	Diuven	Islands (IOI08_islands)	C++11	100 / 100	1779 ms	206600 KB

islands

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;
const int MX=1000010;
const ll inf=2e17;

int n, A[MX], C[MX];
vector<pil> G[MX];
bool done[MX];

ll D[MX];

bool vis[MX];

// list all vertices
void dfs1(int v, vector<int> &V){
    done[v]=true;
    V.push_back(v);
    for(pil &e:G[v]){
        int x=e.first;
        if(done[x]) continue;
        dfs1(x,V);
    }
}

// find cycle 
int found=-1;
int dep[MX], now;
void dfs2(int v, int p, vector<int> &V){
    dep[v]=++now;
    for(pil &e:G[v]){
        int x; ll c; tie(x,c)=e;
        if(p==x) continue;
        if(dep[x]>=0)
            found=x;
        else
            dfs2(x,v,V);
        if(found>=0){
            if(dep[v]>=dep[found]) V.push_back(v);
            return;
        }
    }
    --now;
}

// farthest point
ll dist[MX]; 
int dfs3(int v){
    int res=v;
    for(pil &e:G[v]){
        int x; ll c; tie(x,c)=e;
        if(dist[x]>=0) continue;
        dist[x]=dist[v]+c;
        int y=dfs3(x);
        if(dist[y]>dist[res]) res=y;
    }
    return res;
}
ll solve_tree(vector<int> &V){
    int s=V[0];

    for(int v:V) dist[v]=-1;
    dist[s]=0;
    int u=dfs3(s);

    for(int v:V) dist[v]=-1;
    dist[u]=0;
    int v=dfs3(u);

    return dist[v];
}

bool incyc[MX];
ll arm[MX], scd[MX];
// longest path from v in cyc
void dfs4(int v){
    arm[v]=0;
    for(pil &e:G[v]){
        int x; ll c; tie(x,c)=e;
        if(incyc[x] || arm[x]>=0) continue;
        dfs4(x);
        ll now=arm[x]+c;
        scd[v]=max(scd[v], now);
        if(scd[v]>arm[v]) swap(scd[v], arm[v]);
    }
}

ll Val[2*MX], Len[2*MX], Sum[2*MX];

vector<int> V, cyc;
ll solve(int s){
    // cout<<"\nSOLVE ON "<<s<<'\n';
    V.clear(), cyc.clear();
    dfs1(s, V);

    found=-1, now=0;
    for(int v:V) dep[v]=-1;
    dfs2(s, -1, cyc);

    if(cyc.empty())
        return solve_tree(V);

    ll res=0;

    for(int v:V) arm[v]=-1, scd[v]=0;
    for(int v:cyc) incyc[v]=true, arm[v]=0;
    for(int v:cyc) dfs4(v);
    for(int v:V) res=max(res, arm[v]+scd[v]);

    int sz=cyc.size();
    Sum[0]=0;
    for(int i=0; i<sz; i++){
        int v=cyc[i];
        Val[i]=arm[v];
        int nxt=cyc[(i+1)%sz];
        for(pil &e:G[v])
            if(e.first==nxt) Len[i]=e.second;
        Sum[i+1]=Sum[i]+Len[i];
    }
    for(int i=sz; i<2*sz; i++)
        Sum[i]=Sum[i%sz]+Sum[sz];
    deque<int> Q;
    for(int j=0; j<=2*sz-1; j++){
        int i=j%sz;
        while(!Q.empty() && Q.front()<=j-sz) Q.pop_front();
        if(!Q.empty()){
            int x=Q.front();
            ll now=Val[x%sz] + Val[i] + Sum[j]-Sum[x];
            res=max(res, now);
        }
        while(!Q.empty()){
            int x=Q.back();
            ll a=Val[x%sz]-Sum[x];
            ll b=Val[j%sz]-Sum[j];
            if(a<=b) Q.pop_back();
            else break;
        }
        Q.push_back(j);
    }
    return res;
    for(int i=0; i<sz; i++)
        for(int j=i+1; j<sz; j++){
            ll dist=max(Sum[j]-Sum[i], Sum[sz]+Sum[i]-Sum[j]);
            ll now=dist+Val[i]+Val[j];

            // printf("%d - %d : %lld (%lld)\n", cyc[i], cyc[j], now, dist);
            res=max(res, now);
        }
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int u=1; u<=n; u++){
        int v, c; cin>>v>>c;
        A[u]=v, C[u]=c;
        if(v<u && A[v]==u){
            C[u]=max(C[u], C[v]);
            C[v]=-1;
        }
    }
    for(int i=1; i<=n; i++){
        if(C[i]<0) continue;
        G[i].push_back({A[i], C[i]});
        G[A[i]].push_back({i, C[i]});
    }
    ll ans=0;
    for(int i=1; i<=n; i++){
        if(done[i]) continue;
        ans+=solve(i);
    }
    cout<<ans;
    return 0;
}

Subtask #1
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	23928 KB	Output is correct
2	Correct	25 ms	23928 KB	Output is correct
3	Correct	20 ms	24116 KB	Output is correct
4	Correct	21 ms	24116 KB	Output is correct
5	Correct	22 ms	24116 KB	Output is correct
6	Correct	20 ms	24156 KB	Output is correct
7	Correct	22 ms	24172 KB	Output is correct
8	Correct	21 ms	24172 KB	Output is correct
9	Correct	21 ms	24188 KB	Output is correct
10	Correct	21 ms	24188 KB	Output is correct
11	Correct	21 ms	24192 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	24316 KB	Output is correct
2	Correct	23 ms	24316 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	24316 KB	Output is correct
2	Correct	24 ms	24700 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	25584 KB	Output is correct
2	Correct	49 ms	28920 KB	Output is correct
3	Correct	36 ms	28920 KB	Output is correct
4	Correct	29 ms	28920 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	30524 KB	Output is correct
2	Correct	66 ms	34168 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	125 ms	42988 KB	Output is correct
2	Correct	142 ms	49908 KB	Output is correct
3	Correct	167 ms	61124 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	200 ms	61124 KB	Output is correct
2	Correct	280 ms	87520 KB	Output is correct
3	Correct	310 ms	97828 KB	Output is correct
4	Correct	387 ms	119232 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	452 ms	119232 KB	Output is correct
2	Correct	1328 ms	164496 KB	Output is correct
3	Correct	397 ms	164496 KB	Output is correct
4	Correct	564 ms	164496 KB	Output is correct
5	Correct	541 ms	164496 KB	Output is correct
6	Correct	1616 ms	164496 KB	Output is correct
7	Correct	597 ms	171088 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	649 ms	171088 KB	Output is correct
2	Correct	639 ms	171088 KB	Output is correct
3	Correct	690 ms	206600 KB	Output is correct
4	Correct	374 ms	206600 KB	Output is correct
5	Correct	528 ms	206600 KB	Output is correct
6	Correct	486 ms	206600 KB	Output is correct
7	Correct	1779 ms	206600 KB	Output is correct

답안 #53888

Compilation message