Submission #384341

#	Time	Username	Problem	Language	Result	Execution time	Memory
384341		jjang36524	Dreaming (IOI13_dreaming)	C++14	100 / 100	128 ms	24940 KiB

dreaming

#include "dreaming.h"
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

int maxt[101000];
int vis[100100];
vector<pair<int,int>>l[101000];
int dfs(int n)
{
    if(vis[n])
        return 0;
    vis[n]=1;
    int i;
    for(i=0;i<l[n].size();i++)
    {
        if(!vis[l[n][i].first])
            maxt[n]=max(maxt[n],dfs(l[n][i].first)+l[n][i].second);
    }
    return maxt[n];
}
pair<int,int> dfs2(int n,int t)
{
    int i;
    if(vis[n])
        return {1<<30,1<<30};
    vis[n]=1;
    pair<int,int>an={0,0};

    vector<int>r;
    pair<int,int>mal={0,0};
    for(i=0;i<l[n].size();i++)
    {
         if(vis[l[n][i].first])
            continue;
        r.push_back(-maxt[l[n][i].first]-l[n][i].second);
        mal=max(mal,{maxt[l[n][i].first]+l[n][i].second,i});
    }
    sort(r.begin(),r.end());

    for(i=0;i<min(2,(int)r.size());i++)
    {
        an.first-=r[i];
        if(i==0)
            an.second-=r[i];
    }
    an.second=max(an.second,t);
    for(i=0;i<l[n].size();i++)
    {
        if(vis[l[n][i].first])
            continue;
        int cu=mal.first;
        if(mal.second==i)
        {
            cu=(r.size()>1)?(-r[1]):0;
        }
        auto a=dfs2(l[n][i].first,max(t+l[n][i].second,cu+l[n][i].second));
        an.first=max(an.first,a.first);
        an.second=min(an.second,a.second);
    }
    return an;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    int i;
    for(i=0;i<M;i++)
    {
        l[A[i]].push_back({B[i],T[i]});
        l[B[i]].push_back({A[i],T[i]});
    }
    for(i=0;i<N;i++)
    {
        dfs(i);
    }
    memset(vis,0,sizeof(vis));
    int di=0;
    vector<int>rr;
    for(i=0;i<N;i++)
    {
        if(vis[i])
            continue;
        auto r=dfs2(i,0);
        rr.push_back(-r.second);
        di=max(di,r.first);
    }
    int cr=di;
    sort(rr.begin(),rr.end());
    if(rr.size()>1)
        cr=max(cr,-rr[0]-rr[1]+L);
     if(rr.size()>2)
        cr=max(cr,-rr[1]-rr[2]+L*2);
    return cr;
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs(int)':
dreaming.cpp:16:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(i=0;i<l[n].size();i++)
      |             ~^~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> dfs2(int, int)':
dreaming.cpp:33:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(i=0;i<l[n].size();i++)
      |             ~^~~~~~~~~~~~
dreaming.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(i=0;i<l[n].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