oj.uz

Submission #133915

# Submission time Handle Problem Language Result Execution time Memory
133915 2019-07-21T18:11:41 Z arthurconmy Dreaming (IOI13_dreaming) C++14
0 / 100
 69 ms 10488 KB 
#include <bits/stdc++.h>
 
#ifndef ARTHUR_LOCAL
	#include "dreaming.h"
#endif
 
using namespace std;
using pii=pair<int,int>;
 
#define ff first
#define ss second
 
const int MAXN = 100001;
vector<pii> adj[MAXN];
bool vis[MAXN];
int dis[MAXN];
pii antipode={-1,-1};
bool vis2[MAXN];
int dis2[MAXN];
pii antipode2={-1,-1};
bool vis3[MAXN];
int semi_diam = -1;
 
void dfs1(int v)
{
	vis[v]=1;
 
	for(auto u_raw:adj[v])
	{
		int u=u_raw.ff;
		int d=u_raw.ss;
 
		if(vis[u]) continue;
		dis[u]=dis[v]+d;
		antipode=max(antipode,{dis[u],u});
		dfs1(u);
	}
}
 
void dfs2(int v)
{
	vis2[v]=1;
 
	for(auto u_raw:adj[v])
	{
		int u=u_raw.ff;
		int d=u_raw.ss;
 
		if(vis2[u]) continue;
		dis2[u]=dis2[v]+d;
		antipode2=max(antipode2,{dis2[u],u});
		dfs2(u);
	}
}
 
void dfs3(int v)
{
	vis3[v]=1;
 
	for(auto u_raw:adj[v])
	{
		int u=u_raw.ff;
		int d=u_raw.ss;
 
		if(vis3[u]) continue;
		semi_diam = min(semi_diam,max(antipode2.ff-dis2[u],dis2[u]));
		dfs3(u);
	}
}
 
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
	vector<pii> di_sdi; // all the diameter, semi-diameter pairs
 
	for(int i=0; i<m; i++)
	{
		adj[A[i]].push_back(make_pair(B[i],T[i]));
		adj[B[i]].push_back(make_pair(A[i],T[i]));
	}
 
	for(int i=0; i<n; i++)
	{
		if(vis[i]) continue;
 
		dfs1(i);
 
		if(antipode == make_pair(-1,-1))
		{
			di_sdi.push_back({0,0});
			continue;
		}
 
		dfs2(antipode.ss);
 
		// cout << i << " " << antipode.ss << " " << antipode2.ss << " " << antipode2.ff << endl;
 
		semi_diam=antipode2.ff-dis2[antipode2.ss];
		dfs3(antipode2.ss); // don't think that this need be from antipode2.ss
 
		di_sdi.push_back({semi_diam,antipode2.ff});
 
		antipode={-1,-1};
		antipode2={-1,-1};
	}
 
	// for(auto SD:di_sdi)
	// {
	// 	cout << SD.ff << " " << SD.ss << endl;
	// }
 
	sort(di_sdi.rbegin(),di_sdi.rend());
 
	int ans=0;
 
	for(auto SD:di_sdi) ans=max(ans,SD.ss);
 
	if(di_sdi.size()>=3) ans=max(ans,l+l+di_sdi[1].ff+di_sdi[2].ff);
	if(di_sdi.size()>=2) ans=max(ans,l+di_sdi[0].ff+di_sdi[1].ff);
 
	// cout << ans << endl;
 
	return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs3(int)':
dreaming.cpp:63:7: warning: unused variable 'd' [-Wunused-variable]
   int d=u_raw.ss;
       ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10488 KB Output is correct
2 Correct 69 ms 10488 KB Output is correct
3 Correct 45 ms 7804 KB Output is correct
4 Correct 12 ms 3832 KB Output is correct
5 Correct 11 ms 3320 KB Output is correct
6 Correct 20 ms 4344 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10488 KB Output is correct
2 Correct 69 ms 10488 KB Output is correct
3 Correct 45 ms 7804 KB Output is correct
4 Correct 12 ms 3832 KB Output is correct
5 Correct 11 ms 3320 KB Output is correct
6 Correct 20 ms 4344 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10488 KB Output is correct
2 Correct 69 ms 10488 KB Output is correct
3 Correct 45 ms 7804 KB Output is correct
4 Correct 12 ms 3832 KB Output is correct
5 Correct 11 ms 3320 KB Output is correct
6 Correct 20 ms 4344 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10488 KB Output is correct
2 Correct 69 ms 10488 KB Output is correct
3 Correct 45 ms 7804 KB Output is correct
4 Correct 12 ms 3832 KB Output is correct
5 Correct 11 ms 3320 KB Output is correct
6 Correct 20 ms 4344 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10488 KB Output is correct
2 Correct 69 ms 10488 KB Output is correct
3 Correct 45 ms 7804 KB Output is correct
4 Correct 12 ms 3832 KB Output is correct
5 Correct 11 ms 3320 KB Output is correct
6 Correct 20 ms 4344 KB Output is correct
7 Incorrect 4 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -