Submission #174663

#	Time	Username	Problem	Language	Result	Execution time	Memory
174663		tinjyu	Dreaming (IOI13_dreaming)	C++14	100 / 100	138 ms	15580 KiB

dreaming

#include "dreaming.h"

#include <iostream>
using namespace std;
long long int e,mi,lo,p,st,en,tmp,n,m,road[100005],map[200005][3],ans,max1,max2,max3,tag[100005];
int find(long long int x,long long int dis,long long int fa)
{
	tag[x]=1;
	//cout<<x<<" "<<dis<<endl;
	long long int c=0;
	if(x==en)c=1;
	if(dis>tmp)
	{
		tmp=dis;
		p=x;
	}
	//cout<<" "<<map[road[x]][0]<<" "<<road[x]<<endl;
	int g=road[x];
	while(g!=-1)
	{
		int now=map[g][0];
		if(now!=fa)
		{
			if(find(now,dis+map[g][2],x)==1)c=1;
		}
		g=map[g][1];
	}
	if(c==1)
	{
		mi=min(mi,max(dis,lo-dis));
	}
	return c;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n=N;
	m=M;
	for(int i=0;i<n;i++)road[i]=-1;
	for(int i=0;i<m;i++)
	{
		map[i*2][0]=A[i];
		map[i*2][1]=road[B[i]];
		map[i*2][2]=T[i];
		road[B[i]]=i*2;
		map[i*2+1][0]=B[i];
		map[i*2+1][1]=road[A[i]];
		map[i*2+1][2]=T[i];
		road[A[i]]=i*2+1;
	}
	for(int i=0;i<n;i++)
	{
		if(tag[i]==1)continue;
		e=i;
		//cout<<i<<endl;
		tmp=-1;
		st=-1,en=-1;
		find(i,0,-1);
		st=p;
		tmp=-1;
		
		find(st,0,-1);
		en=p;
		lo=tmp;
		ans=max(ans,lo);
		mi=9999999999999999;
		find(st,0,-1);
		if(mi>max1)
		{
			max3=max2;
			max2=max1;
			max1=mi;
		}
		else if(mi>max2)
		{
			max3=max2;
			max2=mi;
		}
		else if(mi>max3)
		{
			max3=mi;
		}
	}
	if(N-M-1>=2)ans=max(ans,max(max1+max2+L,max2+max3+L*2));
	else if(N-M-1>=1)ans=max(max1+max2+L,ans);
	return ans;
}

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