Submission #3168

#	Time	Username	Problem	Language	Result	Execution time	Memory
3168		cki86201	Dreaming (IOI13_dreaming)	C++98	100 / 100	86 ms	9336 KiB

dreaming

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

int N,M,L;
int Y[100010],tl,inl;
int tmp[100010],Q[100010][3];
int check[100010];
struct line{
    line(){}
    line(int en,int len):en(en),len(len){}
    int en,len;
};
vector <line> edge[100010];

int far(int x)
{
	int fr=1,re=0,ret=x,mx=0;
	Q[0][0]=x;Q[0][1]=0;check[x]=1;
	while(fr!=re){
		int i;
		for(i=0;i<edge[Q[re][0]].size();i++){
			int tx=edge[Q[re][0]][i].en;
			if(check[tx])continue;
			check[tx]=1;
			Q[fr][0]=tx;
			Q[fr][1]=Q[re][1]+edge[Q[re][0]][i].len;
			if(mx<Q[fr][1]){
				mx=Q[fr][1];
				ret=Q[fr][0];
			}
			fr++;
		}
		re++;
	}
	return ret;
}

void solve(int x)
{
	int t=far(x),fr=1,re=0,tp=0;
	Q[0][0]=t;Q[0][1]=0;Q[0][2]=-1;check[t]=2;
	while(fr!=re){
		int i;
		for(i=0;i<edge[Q[re][0]].size();i++){
			int tx=edge[Q[re][0]][i].en;
			if(check[tx]==2)continue;
			check[tx]=2;
			Q[fr][0]=tx;
			Q[fr][1]=Q[re][1]+edge[Q[re][0]][i].len;
			Q[fr][2]=re;
			if(Q[fr][1]>Q[tp][1])tp=fr;
			fr++;
		}
		re++;
	}
	int len=Q[tp][1],tx=0;
	while(Q[tp][2]!=-1){
		if(Q[tp][1]*2>len)tx=Q[tp][1];
		else{tx=min(tx,len-Q[tp][1]);break;}
		tp=Q[tp][2];
	}
	Y[tl]=tx;tl++;
	inl=max(inl,len);
}

int travelTime(int Nn, int Mm, int Ll, int A[], int B[], int T[]){
	N=Nn,M=Mm,L=Ll;
	int i;
	for(i=0;i<M;i++){
		edge[A[i]+1].push_back(line(B[i]+1,T[i]));
		edge[B[i]+1].push_back(line(A[i]+1,T[i]));
	}
	for(i=1;i<=N;i++){
		if(check[i])continue;
		solve(i);
	}
	sort(Y,Y+tl);
	if(tl==1)return inl;
	if(tl==2)return max(inl,L+Y[tl-1]+Y[tl-2]);
	else return max(inl,max(L+Y[tl-1]+Y[tl-2],2*L+Y[tl-2]+Y[tl-3]));
}

Compilation message (stderr)

dreaming.cpp: In function 'int far(int)':
dreaming.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<edge[Q[re][0]].size();i++){
           ~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void solve(int)':
dreaming.cpp:46:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<edge[Q[re][0]].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