oj.uz

Submission #174656

# Submission time Handle Problem Language Result Execution time Memory
174656 2020-01-06T15:21:55 Z tinjyu Dreaming (IOI13_dreaming) C++14
0 / 100
 51 ms 11388 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -