Submission #12819

#	Time	Username	Problem	Language	Result	Execution time	Memory
12819		dohyun0324	Dreaming (IOI13_dreaming)	C++98	100 / 100	111 ms	20216 KiB

dreaming

#include "dreaming.h"
#include<algorithm>
#include<vector>
using namespace std;
int maxx,t,dap,s[100010],w,arr[200010],top,ch[100010],pos[100010],big1[100010],big2[100010];
vector<int>d[100010];
struct data{
    int x,y,c;
    bool operator<(const data&r)const{
        return x<r.x;
    }
}con[200010];
void dfs1(int x,int cost)
{
    int i;
    ch[x]=1;
    if(maxx<cost) maxx=cost, t=x;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]) continue;
        dfs1(con[i].y,cost+con[i].c);
        d[x].push_back(big1[con[i].y]+con[i].c);
    }
    int p=0;
    for(i=0;i<d[x].size();i++){
        if(big1[x]<d[x][i]){big1[x]=d[x][i]; p=i;}
    }
    for(i=0;i<d[x].size();i++){
        if(big2[x]<d[x][i] && i!=p) big2[x]=d[x][i];
    }
}
void dfs2(int x,int gap)
{
    int i;
    ch[x]=2;
    if(dap>max(big1[x],gap)) dap=max(big1[x],gap);
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]==2) continue;
        int maxi=0;
        if(big1[x]==d[x][s[x]]) maxi=max(gap,big2[x]);
        else maxi=max(gap,big1[x]);
        dfs2(con[i].y,maxi+con[i].c);
        s[x]++;
    }
}
void dfs(int x,int cost)
{
    int i;
    ch[x]=3;
    if(maxx<cost) maxx=cost, t=x;
    for(i=pos[x];;i++)
    {
        if(x!=con[i].x) break;
        if(ch[con[i].y]==3) continue;
        dfs(con[i].y,cost+con[i].c);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int i,ans=0;
    for(i=0;i<M;i++)
    {
        A[i]++; B[i]++;
        w++; con[w].x=A[i]; con[w].y=B[i]; con[w].c=T[i];
        w++; con[w].x=B[i]; con[w].y=A[i]; con[w].c=T[i];
    }
    sort(con+1,con+w+1);
    for(i=1;i<=w;i++)
    {
        if(con[i].x!=con[i-1].x) pos[con[i].x]=i;
    }
    for(i=1;i<=N;i++)
    {
        if(ch[i]==0)
        {
            dap=2147483647; maxx=0;
            dfs1(i,0);
            dfs2(i,0);
            maxx=0; dfs(t,0);
            if(ans<maxx) ans=maxx;
            arr[++top]=dap;
        }
    }
    sort(arr+1,arr+top+1);
    if(top==1) return ans;
    if(top==2) return max(ans,arr[1]+arr[2]+L);
    return max(ans,max(arr[top]+arr[top-1]+L,arr[top-1]+arr[top-2]+L*2));
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<d[x].size();i++){
             ~^~~~~~~~~~~~
dreaming.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<d[x].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