Submission #59267

#	Time	Username	Problem	Language	Result	Execution time	Memory
59267		TadijaSebez	Dreaming (IOI13_dreaming)	C++11	100 / 100	140 ms	13088 KiB

dreaming

#include "dreaming.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
const int inf=1e9+7;
int max(int a, int b){ return a>b?a:b;}
int min(int a, int b){ return a>b?b:a;}
bool ckmax(int &a, int b){ int c=a;a=max(a,b);return c!=a;}
bool ckmin(int &a, int b){ int c=a;a=min(a,b);return c!=a;}
const int N=100050;
vector<pair<int,int> > E[N];
int dep[N],par[N];
vector<int> nodes;
bool was[N];
void DFS(int u, int p, int d)
{
	was[u]=1;
	nodes.pb(u);
	dep[u]=dep[p]+d;
	par[u]=p;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		int w=E[u][i].second;
		if(v!=p) DFS(v,u,w);
	}
}
vector<int> sz;
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
	int n,m,u,v,w,i,j,l;
	//scanf("%i %i %i",&n,&m,&l);
	n=N;m=M;l=L;
	for(i=1;i<=m;i++) u=A[i-1],v=B[i-1],w=T[i-1],u++,v++,E[u].pb(mp(v,w)),E[v].pb(mp(u,w));
	int ans=0;
	for(i=1;i<=n;i++) if(!was[i])
	{
		int cen=0,den=0;
		nodes.clear();
		DFS(i,0,0);
		for(j=0;j<nodes.size();j++)
		{
			if(!cen || dep[nodes[j]]>dep[cen]) cen=nodes[j];
		}
		nodes.clear();
		DFS(cen,0,0);
		for(j=0;j<nodes.size();j++)
		{
			if(!den || dep[nodes[j]]>dep[den]) den=nodes[j];
		}
		int dist=dep[den],best=inf;
		for(j=den;j;j=par[j]) ckmin(best,max(dep[j],dist-dep[j]));
		ckmax(ans,dist);
		//printf("%i %i %i %i\n",cen,den,dist,best);
		sz.pb(best);
	}
	sort(sz.rbegin(),sz.rend());
	if(sz.size()==1) return max(sz[0],ans);
	if(sz.size()==2) return max(sz[0]+sz[1]+l,ans);
	return max(ans,max(sz[0]+sz[1]+l,sz[1]+sz[2]+2*l));
}

Compilation message (stderr)

dreaming.cpp: In function 'void DFS(int, int, int)':
dreaming.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<nodes.size();j++)
           ~^~~~~~~~~~~~~
dreaming.cpp:50:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<nodes.size();j++)
           ~^~~~~~~~~~~~~

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