oj.uz

Submission #174650

# Submission time Handle Problem Language Result Execution time Memory
174650 2020-01-06T14:57:07 Z tinjyu Dreaming (IOI13_dreaming) C++14
0 / 100
 56 ms 12684 KB 
#include "dreaming.h"

#include <iostream>
using namespace std;
long long int mi,lo,p,st,en,tmp,n,m,road[100005],map[200005][3],ans,max1,max2,max3,tag[100005];
int find(int x,long long int dis,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;
		//cout<<i<<endl;
		tmp=-1;
		st=-1,en=-1;
		find(i,0,-1);
		st=p;
		tmp=-1;
		mi=999999999999;
		find(st,0,-1);
		en=p;
		lo=tmp;
		ans=max(ans,lo);
		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;
		}
		//cout<<st<<" "<<en<<" "<<lo<<" "<<max1<<" "<<max2<<" "<<max3<<endl;
	}
	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 52 ms 12664 KB Output is correct
2 Correct 56 ms 12684 KB Output is correct
3 Correct 36 ms 8568 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 8 ms 1500 KB Output is correct
6 Correct 15 ms 3064 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 52 ms 12664 KB Output is correct
2 Correct 56 ms 12684 KB Output is correct
3 Correct 36 ms 8568 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 8 ms 1500 KB Output is correct
6 Correct 15 ms 3064 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 52 ms 12664 KB Output is correct
2 Correct 56 ms 12684 KB Output is correct
3 Correct 36 ms 8568 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 8 ms 1500 KB Output is correct
6 Correct 15 ms 3064 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 Incorrect 23 ms 4128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 12664 KB Output is correct
2 Correct 56 ms 12684 KB Output is correct
3 Correct 36 ms 8568 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 8 ms 1500 KB Output is correct
6 Correct 15 ms 3064 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 52 ms 12664 KB Output is correct
2 Correct 56 ms 12684 KB Output is correct
3 Correct 36 ms 8568 KB Output is correct
4 Correct 9 ms 2168 KB Output is correct
5 Correct 8 ms 1500 KB Output is correct
6 Correct 15 ms 3064 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -