Submission #15888

#	Time	Username	Problem	Language	Result	Execution time	Memory
15888		ggoh	Dreaming (IOI13_dreaming)	C++98	100 / 100	105 ms	12340 KiB

dreaming

#include "dreaming.h"
#include<cstdio>
#include<vector>
#include<algorithm>
struct AA{
	int to,cost;
};
std::vector<AA>G[100002];
int ans,i,m,t,st[100002],back[100002],pos,len,K;
bool v[100002],vv[100002];
void dfs(int x,int l)
{
	for(int j=0;j<G[x].size();j++)
	{
		AA u=G[x][j];
		if(!v[u.to])
		{
			if(m<=l+u.cost)
			{
				pos=u.to;m=l+u.cost;
			}
			v[u.to]=1;
			dfs(u.to,l+u.cost);
		}
	}
}
void dfs2(int x,int l)
{
	for(int j=0;j<G[x].size();j++)
	{
		AA u=G[x][j];
		if(!vv[u.to])
		{
			if(m<=l+u.cost)
			{
				pos=u.to;m=l+u.cost;
			}
			vv[u.to]=1;
			back[u.to]=x;
			dfs2(u.to,l+u.cost);
		}
	}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
	for(i=0;i<M;i++)
	{
		G[A[i]+1].push_back({B[i]+1,T[i]});
		G[B[i]+1].push_back({A[i]+1,T[i]});
	}
	for(i=1;i<=N;i++)
	{
		if(!v[i])
		{
			v[i]=1;
			m=0;
			pos=i;
			dfs(i,0);
			m=0;
			back[pos]=-1;
			vv[pos]=1;
			dfs2(pos,0);
			len=std::max(len,m);
			K=0;st[t]=m;
			while(back[pos]!=-1)
			{
				for(int k=0;k<G[pos].size();k++)
				{
					if(G[pos][k].to==back[pos])
					{
						K+=G[pos][k].cost;
						pos=back[pos];
						break;
					}
				}
				st[t]=std::min(st[t],std::max(K,m-K));
			}
			t++;
		}
	}
	std::sort(st,st+t);
	ans=len;
	if(t>1)ans=std::max(st[t-1]+st[t-2]+L,ans);
	if(t>2)ans=std::max(ans,st[t-2]+2*L+st[t-3]);
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<G[x].size();j++)
              ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<G[x].size();j++)
              ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<G[pos].size();k++)
                 ~^~~~~~~~~~~~~~

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