Submission #16591

#	Time	Username	Problem	Language	Result	Execution time	Memory
16591		CodingBug	Dreaming (IOI13_dreaming)	C++98	100 / 100	77 ms	12132 KiB

dreaming

#include "dreaming.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#define M 100000
using namespace std;

int sta[M*2+1],chi[M*2+1],wei[M*2+1],nxt[M*2+1];
int n,m,l,d[2][M+1],v[2][M+1],itr;
vector<int> vec;
bool ch[M+1];

void addEdge(int x,int y,int w){
    nxt[++m]=sta[x];
    sta[x]=m;
    chi[m]=y;
    wei[m]=w;
}

int DFS1(int x,int p){
    int i;

    for(i=sta[x];i;i=nxt[i]){
        if(chi[i]!=p){
            int k=DFS1(chi[i],x)+wei[i];
            if(d[0][x]<k){
                d[1][x]=d[0][x];
                v[1][x]=v[0][x];
                d[0][x]=k;
                v[0][x]=i;
            }
            else if(d[1][x]<k){
                d[1][x]=k;
                v[1][x]=i;
            }
        }
    }
    return d[0][x];
}

int DFS2(int x,int s,int p){
    int i,ret;

    if(d[0][x]<s){
        d[1][x]=d[0][x];
        v[1][x]=v[0][x];
        d[0][x]=s;
        v[0][x]=-1;
    }
    else if(d[1][x]<s){
        d[1][x]=s;
        v[1][x]=-1;
    }
    ret=d[0][x];
    ch[x]=true;

    for(i=sta[x];i;i=nxt[i]){
        if(chi[i]!=p){
            int k;
            if(v[0][x]!=i){
                k=DFS2(chi[i],d[0][x]+wei[i],x);
            }
            else{
                k=DFS2(chi[i],d[1][x]+wei[i],x);
            }
            ret=min(ret,k);
        }
    }
    itr=max(itr,d[0][x]+d[1][x]);
    return ret;
}


int travelTime(int _n, int _m, int _l, int A[], int B[], int T[]) {
    int i;
    n=_n; l=_l;
    for(i=0;i<_m;i++){
        addEdge(A[i],B[i],T[i]);
        addEdge(B[i],A[i],T[i]);
    }
    for(i=0;i<n;i++){
        if(!ch[i]){
            DFS1(i,-1);
            vec.push_back(DFS2(i,0,-1));
        }
    }
    int mx1=-1,mx2=-1,mx3=-1;
    for(i=0;i<vec.size();i++){
        if(mx3<vec[i]){mx3=vec[i];}
        if(mx2<vec[i]){mx3=mx2;mx2=vec[i];}
        if(mx1<vec[i]){mx2=mx1;mx1=vec[i];}
    }
    if(mx2==-1) return itr;
    if(mx3==-1) return max(itr,mx1+mx2+l);
    return max(itr,max(mx1+mx2+l,mx2+mx3+l*2));
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:88:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<vec.size();i++){
             ~^~~~~~~~~~~

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