oj.uz

Submission #259383

# Submission time Handle Problem Language Result Execution time Memory
259383 2020-08-07T17:24:14 Z uacoder123 Dreaming (IOI13_dreaming) C++14
32 / 100
 98 ms 19704 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;

lli n,m,l,ans=0,vis[100001],co=0,ans1=0;
vector<iii> al[100001];
vi v;
lli dfs(lli node,lli p)
{
	vis[node]=1;
	co++;
	for(lli i=0;i<al[node].size();++i)
	{
		if(!vis[al[node][i].S.F])
		{
			al[node][i].F=dfs(al[node][i].S.F,node);
			al[node][i].F+=al[node][i].S.S;
		}
	}
	sort(all(al[node]));
	if(al[node].size()>1)
		ans1=max(ans1,al[node].back().F+al[node][al[node].size()-2].F);
	else
		ans1=max(ans1,al[node].back().F);
	return(al[node].back().F);
}
void dfs2(lli node,lli p)
{
	sort(all(al[node]));
	lli to=al[node].back().S.F;
	ans=min(ans,al[node].back().F);
	if(to==p)
		return;
	for(lli i=0;i<al[to].size();++i)
	{
		if(al[to][i].S.F==node)
		{
			al[to][i].F=al[node][al[node].size()-2].F+al[to][i].S.S;
			break;
		}
	}
	dfs2(to,node);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
	n=N;
	m=M;
	l=L;
	for(lli i=0;i<m;++i)
	{
		al[A[i]].pb(mp(0,mp(B[i],T[i])));
		al[B[i]].pb(mp(0,mp(A[i],T[i])));
		co+=T[i];
	}
	for(lli i=0;i<n;++i)
	{
		if(al[i].size()>2)
			exit(1);
		al[i].pb(mp(0,mp(i,i)));
	}
	for(lli i=0;i<n;++i)
	{
		if(!vis[i]) 
		{
			dfs(i,i);
			ans=10000000000000000;
			dfs2(i,i);
			v.pb(ans);
		}
	}
	sort(all(v));
	ans=v.back();
	if(v.size()>1)
		ans=v.back()+v[v.size()-2]+l;
	if(v.size()>2)
		ans=max(ans,2*l+v[v.size()-2]+v[v.size()-3]);
	ans1=max(ans1,ans);
	return(ans1);
}

Compilation message

dreaming.cpp: In function 'lli dfs(lli, lli)':
dreaming.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(lli i=0;i<al[node].size();++i)
              ~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(lli, lli)':
dreaming.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(lli i=0;i<al[to].size();++i)
              ~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19704 KB Output is correct
2 Correct 98 ms 19360 KB Output is correct
3 Correct 61 ms 15352 KB Output is correct
4 Correct 12 ms 5120 KB Output is correct
5 Correct 9 ms 4352 KB Output is correct
6 Correct 20 ms 6400 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 37 ms 9868 KB Output is correct
9 Correct 62 ms 12960 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 76 ms 15224 KB Output is correct
12 Correct 89 ms 17400 KB Output is correct
13 Correct 2 ms 2944 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19704 KB Output is correct
2 Correct 98 ms 19360 KB Output is correct
3 Correct 61 ms 15352 KB Output is correct
4 Correct 12 ms 5120 KB Output is correct
5 Correct 9 ms 4352 KB Output is correct
6 Correct 20 ms 6400 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 37 ms 9868 KB Output is correct
9 Correct 62 ms 12960 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 76 ms 15224 KB Output is correct
12 Correct 89 ms 17400 KB Output is correct
13 Correct 2 ms 2944 KB Output is correct
14 Runtime error 2 ms 2688 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19704 KB Output is correct
2 Correct 98 ms 19360 KB Output is correct
3 Correct 61 ms 15352 KB Output is correct
4 Correct 12 ms 5120 KB Output is correct
5 Correct 9 ms 4352 KB Output is correct
6 Correct 20 ms 6400 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 37 ms 9868 KB Output is correct
9 Correct 62 ms 12960 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 76 ms 15224 KB Output is correct
12 Correct 89 ms 17400 KB Output is correct
13 Correct 2 ms 2944 KB Output is correct
14 Runtime error 2 ms 2688 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9716 KB Output is correct
2 Correct 37 ms 9720 KB Output is correct
3 Correct 47 ms 9592 KB Output is correct
4 Correct 53 ms 9720 KB Output is correct
5 Correct 37 ms 9592 KB Output is correct
6 Correct 43 ms 10608 KB Output is correct
7 Correct 41 ms 9976 KB Output is correct
8 Correct 40 ms 9588 KB Output is correct
9 Correct 38 ms 9464 KB Output is correct
10 Correct 57 ms 9848 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 14 ms 7676 KB Output is correct
13 Correct 14 ms 7804 KB Output is correct
14 Correct 14 ms 7676 KB Output is correct
15 Correct 23 ms 7672 KB Output is correct
16 Correct 14 ms 7800 KB Output is correct
17 Correct 14 ms 7548 KB Output is correct
18 Correct 14 ms 7800 KB Output is correct
19 Correct 14 ms 7676 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 2 ms 2688 KB Output is correct
22 Correct 2 ms 2816 KB Output is correct
23 Correct 14 ms 7676 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19704 KB Output is correct
2 Correct 98 ms 19360 KB Output is correct
3 Correct 61 ms 15352 KB Output is correct
4 Correct 12 ms 5120 KB Output is correct
5 Correct 9 ms 4352 KB Output is correct
6 Correct 20 ms 6400 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 37 ms 9868 KB Output is correct
9 Correct 62 ms 12960 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 76 ms 15224 KB Output is correct
12 Correct 89 ms 17400 KB Output is correct
13 Correct 2 ms 2944 KB Output is correct
14 Runtime error 2 ms 2688 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19704 KB Output is correct
2 Correct 98 ms 19360 KB Output is correct
3 Correct 61 ms 15352 KB Output is correct
4 Correct 12 ms 5120 KB Output is correct
5 Correct 9 ms 4352 KB Output is correct
6 Correct 20 ms 6400 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 37 ms 9868 KB Output is correct
9 Correct 62 ms 12960 KB Output is correct
10 Correct 2 ms 2816 KB Output is correct
11 Correct 76 ms 15224 KB Output is correct
12 Correct 89 ms 17400 KB Output is correct
13 Correct 2 ms 2944 KB Output is correct
14 Runtime error 2 ms 2688 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -