oj.uz

Submission #15883

# Submission time Handle Problem Language Result Execution time Memory
15883 2015-08-01T05:38:28 Z ggoh Dreaming (IOI13_dreaming) C++
18 / 100
 57 ms 11768 KB 
#include "dreaming.h"
#include<cstdio>
#include<vector>
#include<algorithm>
struct AA{
	int to,cost;
};
std::vector<AA>G[100002];
int ans,i,m,t,st[100002],back[100002],backlen[100002],pos,len,K;
bool v[100002],vv[100002];
void dfs(int x,int l)
{
	for(int j=0;j<G[x].size();j++)
	{
		AA u=G[x][j];
		if(!v[u.to])
		{
			if(m<=l+u.cost)
			{
				pos=u.to;m=l+u.cost;
			}
			v[u.to]=1;
			dfs(u.to,l+u.cost);
		}
	}
}
void dfs2(int x,int l)
{
	for(int j=0;j<G[x].size();j++)
	{
		AA u=G[x][j];
		if(!vv[u.to])
		{
			if(m<=l+u.cost)
			{
				pos=u.to;m=l+u.cost;
			}
			
			vv[u.to]=1;
			dfs2(u.to,l+u.cost);
		}
		else back[x]=u.to,backlen[x]=u.cost;
	}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
	for(i=0;i<M;i++)
	{
		G[A[i]].push_back({B[i],T[i]});
		G[B[i]].push_back({A[i],T[i]});
	}
	for(i=1;i<=N;i++)
	{
		if(!v[i])
		{
			v[i]=1;
			m=0;
			pos=i;
			dfs(i,0);
			m=0;
			back[pos]=-1;
			vv[pos]=1;
			dfs2(pos,0);
			len=std::max(len,m);
			K=0;st[t]=m;
			while(back[pos]!=-1)
			{
				K+=backlen[pos];
				st[t]=std::min(st[t],std::max(K,m-K));
				pos=back[pos];
			}
			t++;
		}
	}
	if(t==1)ans=std::max(st[0],len);
	else if(t==2)ans=std::max(st[0]+st[1]+L,len);
	else 
	{
		std::sort(st,st+t);
		int m1=st[t-1],m2=st[t-2],m3=st[t-3];
		ans=std::max(len,m1+L+m2);
		ans=std::max(ans,m2+2*L+m3);
	}
	return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<G[x].size();j++)
              ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<G[x].size();j++)
              ~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11768 KB Output is correct
2 Correct 57 ms 11740 KB Output is correct
3 Correct 38 ms 8568 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 9 ms 3456 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11768 KB Output is correct
2 Correct 57 ms 11740 KB Output is correct
3 Correct 38 ms 8568 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 9 ms 3456 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11768 KB Output is correct
2 Correct 57 ms 11740 KB Output is correct
3 Correct 38 ms 8568 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 9 ms 3456 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6136 KB Output is correct
2 Correct 28 ms 6108 KB Output is correct
3 Correct 27 ms 6228 KB Output is correct
4 Correct 27 ms 6144 KB Output is correct
5 Correct 31 ms 6108 KB Output is correct
6 Correct 30 ms 6392 KB Output is correct
7 Correct 26 ms 6272 KB Output is correct
8 Correct 29 ms 6144 KB Output is correct
9 Correct 29 ms 6144 KB Output is correct
10 Correct 28 ms 6264 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 7 ms 3968 KB Output is correct
13 Correct 7 ms 4096 KB Output is correct
14 Correct 7 ms 3968 KB Output is correct
15 Correct 6 ms 3968 KB Output is correct
16 Correct 7 ms 3968 KB Output is correct
17 Correct 6 ms 3712 KB Output is correct
18 Correct 7 ms 4096 KB Output is correct
19 Correct 6 ms 3968 KB Output is correct
20 Correct 3 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 4 ms 2688 KB Output is correct
23 Correct 7 ms 3968 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11768 KB Output is correct
2 Correct 57 ms 11740 KB Output is correct
3 Correct 38 ms 8568 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 9 ms 3456 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11768 KB Output is correct
2 Correct 57 ms 11740 KB Output is correct
3 Correct 38 ms 8568 KB Output is correct
4 Correct 11 ms 4096 KB Output is correct
5 Correct 9 ms 3456 KB Output is correct
6 Correct 16 ms 4608 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -