Submission #14796

#	Time	Username	Problem	Language	Result	Execution time	Memory
14796		progressive	Dreaming (IOI13_dreaming)	C++98	18 / 100	60 ms	15092 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <algorithm>
using namespace std;
  
static const int MAXN=100100;
vector<pair<int,int> > conn[MAXN];
static int color[MAXN];
static int tp=0;
static int hdist[MAXN];
static int dist[MAXN];
static int parent[MAXN];
vector<int> samecolor[MAXN];
vector<int> radius;
void colordfs(int a,int pa,int c)
{
    color[a]=c;
    samecolor[c].push_back(a);
    for(int i=0;i<conn[a].size();i++)
    {
        int target=conn[a][i].first;
        if(target==pa) continue;
        hdist[target]=hdist[a]+conn[a][i].second;
        colordfs(target,a,c);
    }
}
void dfs(int a,int pa)
{
    parent[a]=pa;
    for(int i=0;i<conn[a].size();i++)
    {
        int target=conn[a][i].first;
        if(target==pa) continue;
        dist[target]=dist[a]+conn[a][i].second;
        dfs(target,a);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for(int i=0;i<M;i++)
    {
        conn[A[i]].push_back(make_pair(B[i],T[i]));
        conn[B[i]].push_back(make_pair(A[i],T[i]));
    }
    for(int i=0;i<N;i++)
        if(!color[i]) colordfs(i,-1,++tp);
    for(int i=1;i<=tp;i++)
    {
        int furthest=samecolor[i][0];
        for(int j=1;j<samecolor[i].size();j++)
            if(hdist[furthest]<hdist[samecolor[i][j]]) furthest=samecolor[i][j];
        dfs(furthest,-1);
        int dia=furthest;
        for(int j=0;j<samecolor[i].size();j++)
            if(dist[dia]<dist[samecolor[i][j]]) dia=samecolor[i][j];
        int radii=dist[dia];
        int res=dist[dia];
        int getr=dia;
        while(~dia)
        {
            res=min(res,max(radii-dist[dia],dist[dia]));
            dia=parent[dia];
        }
        radius.push_back(res);
    }
    sort(radius.begin(),radius.end());
    reverse(radius.begin(),radius.end());
    if(tp==1) return radius[0];
    if(tp==2) return radius[0]+radius[1]+L;
    return max(radius[0]+radius[1]+L,radius[1]+radius[2]+2*L);
}

Compilation message (stderr)

dreaming.cpp: In function 'void colordfs(int, int, int)':
dreaming.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<conn[a].size();i++)
                 ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<conn[a].size();i++)
                 ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<samecolor[i].size();j++)
                     ~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<samecolor[i].size();j++)
                     ~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp:58:13: warning: unused variable 'getr' [-Wunused-variable]
         int getr=dia;
             ^~~~

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