Submission #133907

#	Time	Username	Problem	Language	Result	Execution time	Memory
133907		arthurconmy	Dreaming (IOI13_dreaming)	C++14	18 / 100	64 ms	10488 KiB

dreaming

#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;

		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=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.ff);

	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;
}

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