Submission #573961

#	Time	Username	Problem	Language	Result	Execution time	Memory
573961		mosiashvililuka	Dreaming (IOI13_dreaming)	C++14	100 / 100	125 ms	17076 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N=1000000009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,L,pas,bo[100009],pi,dp[100009],dp2[100009],MX[100009];
pair <int, int> DP[100009];
vector <pair <int, int> > v[100009];
pair <int, int> p[100009];
void UPD(int q, int w){
    if(DP[q].first<=w){
        DP[q].second=DP[q].first;DP[q].first=w;
    }else{
        if(DP[q].second<w) DP[q].second=w;
    }
}
void dfs2(int q, int w, int rr){
    bo[q]=2;
    if(w!=0){
        dp2[q]=dp2[w]+rr;
        int qw=0;
        if(DP[w].first!=dp[q]+rr) qw=DP[w].first; else qw=DP[w].second;
        dp2[q]=max(dp2[q],rr+qw);
    }
    for(vector <pair <int, int> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if(bo[(*it).first]==2) continue;
        dfs2((*it).first,q,(*it).second);
    }
    MX[i]=min(MX[i],max(dp[q],dp2[q]));
}
void dfs(int q){
    bo[q]=1;
    for(vector <pair <int, int> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if(bo[(*it).first]==1) continue;
        dfs((*it).first);
        dp[q]=max(dp[q],dp[(*it).first]+(*it).second);
        UPD(q,dp[(*it).first]+(*it).second);
    }
}
void DFS(int q, int w, int rr){
    if(d<rr){
        c=q;d=rr;
    }
    for(vector <pair <int, int> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it).first==w) continue;
        DFS((*it).first,q,rr+(*it).second);
    }
}
int travelTime(int NN, int MM, int LL, int AA[], int BB[], int TT[]) {
    a=NN;b=MM;L=LL;
    for(i=1; i<=b; i++){
        AA[i-1]++;BB[i-1]++;
        v[AA[i-1]].push_back({BB[i-1],TT[i-1]});
        v[BB[i-1]].push_back({AA[i-1],TT[i-1]});
    }
    for(i=1; i<=a; i++){
        MX[i]=N;
    }
    for(i=1; i<=a; i++){
        if(bo[i]==1) continue;
        dfs(i);
    }
    for(i=1; i<=a; i++){
        if(bo[i]==2) continue;
        dfs2(i,0,0);
        pi++;p[pi]={MX[i],i};
    }
    sort(p+1,p+pi+1);
    for(ii=1; ii<=pi; ii++){
        i=p[ii].second;
        //cout<<i<<" i\n";
        c=i;d=0;
        DFS(i,0,0);
        //cout<<c<<" "<<d<<"\n";
        e=c;
        c=e;d=0;
        DFS(e,0,0);
        //cout<<c<<" "<<d<<"\n";
        pas=max(pas,d);
    }
    /*for(ii=1; ii<=pi; ii++){
        cout<<p[ii].first<<" "<<p[ii].second<<" P\n";
    }*/
    if(pi>=2){
        pas=max(pas,p[pi].first+p[pi-1].first+L);
    }
    if(pi>=3){
        pas=max(pas,p[pi-1].first+p[pi-2].first+2*L);
    }
    return pas;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23