oj.uz

Submission #39090

# Submission time Handle Problem Language Result Execution time Memory
39090 2018-01-09T09:42:22 Z faustaadp Dreaming (IOI13_dreaming) C++14
18 / 100
 109 ms 35192 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,b[1010101],ma1,ma2,i1,hz,a[1010101];
vector<pair<ll,ll> > v[1010101];
vector<ll> v1;
ll rmt(ll aa,ll bb)
{
	if(bb>ma1)
	{
		ma1=bb;
		i1=aa;
	}
	b[aa]=1;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(b[v[aa][ii].fi]==0)
		{
			rmt(v[aa][ii].fi,bb+v[aa][ii].se);
		}
	}
}
ll rct(ll aa,ll bb)
{
	ma2=max(ma2,bb);
	b[aa]=2;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(b[v[aa][ii].fi]==1)
		{
			rct(v[aa][ii].fi,bb+v[aa][ii].se);
		}
	}
}
ll rrt(ll aa,ll bb,ll cc)
{
	a[cc]=bb;
	if(bb==ma2)
	{
		ll ii;
		for(ii=1;ii<=cc;ii++)
		{
			hz=min(hz,max(ma2-a[ii],a[ii]));
		}
	}
	b[aa]=3;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(b[v[aa][ii].fi]==2)
		{
			rrt(v[aa][ii].fi,bb+v[aa][ii].se,cc+1);
		}
	}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(i=0;i<M;i++)
	{
		v[A[i]].pb(mp(B[i],T[i]));
		v[B[i]].pb(mp(A[i],T[i]));
	}
	for(i=0;i<N;i++)
	{
		if(b[i]==0)
		{
			ma1=0;
			ma2=0;
			hz=10e17;
			rmt(i,0);
			rct(i1,0);
			rrt(i1,0,1);
			v1.pb(hz);
		//	cout<<hz<<"\n";
		}
	}
	sort(v1.begin(),v1.end());
	reverse(v1.begin(),v1.end());
	if(v1.size()==1)
		return v1[0];
	else
	if(v1.size()==2)
		return v1[0]+v1[1]+L;
	else
		return max(v1[0]+v1[1]+L,v1[1]+v1[2]+L+L);
    return 42;
}

Compilation message

dreaming.cpp: In function 'long long int rmt(long long int, long long int)':
dreaming.cpp:21:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
dreaming.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dreaming.cpp: In function 'long long int rct(long long int, long long int)':
dreaming.cpp:34:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
dreaming.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dreaming.cpp: In function 'long long int rrt(long long int, long long int, long long int)':
dreaming.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
dreaming.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 35192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 35192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 35192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 27768 KB Output is correct
2 Correct 51 ms 27852 KB Output is correct
3 Correct 48 ms 27768 KB Output is correct
4 Correct 51 ms 27768 KB Output is correct
5 Correct 52 ms 27768 KB Output is correct
6 Correct 52 ms 28404 KB Output is correct
7 Correct 51 ms 27940 KB Output is correct
8 Correct 52 ms 27768 KB Output is correct
9 Correct 51 ms 27736 KB Output is correct
10 Correct 55 ms 27892 KB Output is correct
11 Correct 23 ms 24064 KB Output is correct
12 Correct 29 ms 26096 KB Output is correct
13 Correct 27 ms 26104 KB Output is correct
14 Correct 31 ms 25976 KB Output is correct
15 Correct 28 ms 25968 KB Output is correct
16 Correct 29 ms 25976 KB Output is correct
17 Correct 27 ms 25840 KB Output is correct
18 Correct 29 ms 26104 KB Output is correct
19 Correct 28 ms 25976 KB Output is correct
20 Correct 22 ms 24056 KB Output is correct
21 Correct 22 ms 24064 KB Output is correct
22 Correct 23 ms 24192 KB Output is correct
23 Correct 27 ms 25968 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 35192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 35192 KB Output isn't correct
2 Halted 0 ms 0 KB -