답안 #174656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
174656	2020-01-06T15:21:55 Z	tinjyu	꿈 (IOI13_dreaming)	C++14	0 / 100	51 ms	11388 KB

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;
	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;
		}
	}
	ans=max(ans,max(max1+max2+L,max2+max3+L*2));
	return ans;
}

Subtask #1

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	11384 KB	Output is correct
2	Correct	51 ms	11388 KB	Output is correct
3	Correct	34 ms	7540 KB	Output is correct
4	Correct	9 ms	1912 KB	Output is correct
5	Correct	8 ms	1400 KB	Output is correct
6	Correct	15 ms	2680 KB	Output is correct
7	Incorrect	2 ms	376 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	11384 KB	Output is correct
2	Correct	51 ms	11388 KB	Output is correct
3	Correct	34 ms	7540 KB	Output is correct
4	Correct	9 ms	1912 KB	Output is correct
5	Correct	8 ms	1400 KB	Output is correct
6	Correct	15 ms	2680 KB	Output is correct
7	Incorrect	2 ms	376 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	11384 KB	Output is correct
2	Correct	51 ms	11388 KB	Output is correct
3	Correct	34 ms	7540 KB	Output is correct
4	Correct	9 ms	1912 KB	Output is correct
5	Correct	8 ms	1400 KB	Output is correct
6	Correct	15 ms	2680 KB	Output is correct
7	Incorrect	2 ms	376 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	3724 KB	Output is correct
2	Correct	19 ms	4128 KB	Output is correct
3	Correct	19 ms	4088 KB	Output is correct
4	Correct	21 ms	4088 KB	Output is correct
5	Correct	18 ms	4088 KB	Output is correct
6	Correct	20 ms	4216 KB	Output is correct
7	Correct	20 ms	4216 KB	Output is correct
8	Correct	19 ms	3960 KB	Output is correct
9	Correct	18 ms	3976 KB	Output is correct
10	Correct	22 ms	4344 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	5 ms	1916 KB	Output is correct
13	Correct	5 ms	1912 KB	Output is correct
14	Correct	5 ms	1912 KB	Output is correct
15	Correct	5 ms	1912 KB	Output is correct
16	Correct	5 ms	1912 KB	Output is correct
17	Correct	5 ms	1912 KB	Output is correct
18	Correct	5 ms	1912 KB	Output is correct
19	Correct	5 ms	1912 KB	Output is correct
20	Incorrect	2 ms	376 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	11384 KB	Output is correct
2	Correct	51 ms	11388 KB	Output is correct
3	Correct	34 ms	7540 KB	Output is correct
4	Correct	9 ms	1912 KB	Output is correct
5	Correct	8 ms	1400 KB	Output is correct
6	Correct	15 ms	2680 KB	Output is correct
7	Incorrect	2 ms	376 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #6

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	11384 KB	Output is correct
2	Correct	51 ms	11388 KB	Output is correct
3	Correct	34 ms	7540 KB	Output is correct
4	Correct	9 ms	1912 KB	Output is correct
5	Correct	8 ms	1400 KB	Output is correct
6	Correct	15 ms	2680 KB	Output is correct
7	Incorrect	2 ms	376 KB	Output isn't correct
8	Halted	0 ms	0 KB	-