Submission #133967

#	Time	Username	Problem	Language	Result	Execution time	Memory
133967		arthurconmy	Dreaming (IOI13_dreaming)	C++14	100 / 100	136 ms	12796 KiB

dreaming

#include <bits/stdc++.h>
 
#ifndef ARTHUR_LOCAL
	#include "dreaming.h"
#endif
 
using namespace std;
using pii=pair<int,int>;
using vi=vector<int>;
 
#define ff first
#define ss second
 
const int MAXN = 100001;
 
vector<pair<int,int>> adj[MAXN];
 
bool vis[MAXN];
int dis[MAXN];
pair<int,int> antipode={-1,-1};
 
bool vis2[MAXN];
int dis2[MAXN];
pair<int,int> antipode2={-1,-1};
 
bool vis3[MAXN];
int semi_diam = -1;

bool found_end=false;
 
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;
 
	if(v==antipode2.ss)
	{
		found_end=1;
	}

	for(auto u_raw:adj[v])
	{
		if(found_end) break;

		int u=u_raw.ff;
 
		if(vis3[u]) continue;
		dfs3(u);
	}

	if(found_end)
	{
		semi_diam=min(semi_diam,max(antipode2.ff-dis2[v],dis2[v]));
	}
}
 
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
	vector<pair<int,int>> di_sdi; // aint the diameter, semi-diameter pairs
 
	for(int i=0; i<m; i++)
	{
		adj[A[i]].push_back(make_pair(B[i],int(T[i])));
		adj[B[i]].push_back(make_pair(A[i],int(T[i])));
	}
 
	for(int i=0; i<n; i++)
	{
		if(vis[i]) continue;
 
		dfs1(i);
 
		if(antipode == make_pair(int(-1),-1))
		{
			di_sdi.push_back({0,0});
			continue;
		}
 
		dfs2(antipode.ss);
 
		found_end=0;
		semi_diam=int(1e9);
		dfs3(antipode.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,int(l + l) + di_sdi[1].ff + di_sdi[2].ff);
	if(di_sdi.size()>=2) ans=max(ans,int(l) + di_sdi[0].ff + di_sdi[1].ff);
 
	// cout << ans << endl;
 
	return ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23