Submission #133917

#	Time	Username	Problem	Language	Result	Execution time	Memory
133917		arthurconmy	Dreaming (IOI13_dreaming)	C++14	32 / 100	90 ms	12536 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>;
using ll = long long;

#define ff first
#define ss second

const int MAXN = 100001;

vector<pair<int,ll>> adj[MAXN];

bool vis[MAXN];
ll dis[MAXN];
pair<ll,int> antipode={ll(-1),-1};

bool vis2[MAXN];
ll dis2[MAXN];
pair<ll,int> antipode2={ll(-1),-1};

bool vis3[MAXN];
ll semi_diam = -1;

void dfs1(int v)
{
	vis[v]=1;

	for(auto u_raw:adj[v])
	{
		int u=u_raw.ff;
		ll 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;
		ll 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;

		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<pair<ll,ll>> di_sdi; // all the diameter, semi-diameter pairs

	for(int i=0; i<m; i++)
	{
		adj[A[i]].push_back(make_pair(B[i],ll(T[i])));
		adj[B[i]].push_back(make_pair(A[i],ll(T[i])));
	}

	for(int i=0; i<n; i++)
	{
		if(vis[i]) continue;

		dfs1(i);

		if(antipode == make_pair(ll(-1),-1))
		{
			di_sdi.push_back({0,0});
			continue;
		}

		dfs2(antipode.ss);

		semi_diam=max(antipode2.ff-dis[antipode2.ss],dis[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());

	ll ans=0;

	for(auto SD:di_sdi) ans=max(ans,SD.ss);
	if(di_sdi.size()>=3) ans=max(ans,ll(l + l) + di_sdi[1].ff + di_sdi[2].ff);
	if(di_sdi.size()>=2) ans=max(ans,ll(l) + di_sdi[0].ff + di_sdi[1].ff);

	// cout << ans << endl;

	return ans;
}

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