Submission #1106262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106262		starchan	Dreaming (IOI13_dreaming)	C++17	65 / 100	49 ms	26140 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back

const int MX = 1e5+5;
const int INF = 2e9;

vector<in> adj[MX];

vector<array<int, 4>> rec[MX];

int dp[MX];

int dp2[MX];

vector<int> vis;

void dfs(int u, int p)
{
	dp[u] = 0;
	vis[u] = 1;
	for(auto [v, w]: adj[u])
	{
		if(v==p) continue;
		dfs(v, u);
		dp[u] = max(dp[v]+w, dp[u]);
		rec[u].pb({v, w, dp[u], dp[v]+w});
	}
	int s = -INF;
	int N = rec[u].size();
	for(int i = N-1; i >= 0; i--)
	{
		s = max(s, rec[u][i][3]);
		rec[u][i][3] = max(s, rec[u][i][3]);
	}
	return;
}

void dfs2(int u, int p, int CR, int &mn, int &mx)
{
	dp2[u] = max(dp[u], CR);
	mn = min(mn, dp2[u]);
	mx = max(mx, dp2[u]);
	if(rec[u].empty())
		return;
	int N = rec[u].size();
	for(int i = 0; i < N; i++)
	{
		int v = rec[u][i][0];
		int s = CR;
		if((i > 0))
			s = max(s, rec[u][i-1][2]);
		if((i < (N-1)))
			s = max(s, rec[u][i+1][3]);
		dfs2(v, u, s+rec[u][i][1], mn, mx);
	}
	return;
}

int travelTime(int n, int m, int L, int a[], int b[], int t[])
{
	for(int i = 0; i < n; i++)
	{
		adj[i].clear();
		rec[i].clear();
	}
	vis.assign(n, 0);
	for(int i = 0; i < m; i++)
	{
		adj[a[i]].pb({b[i], t[i]});
		adj[b[i]].pb({a[i], t[i]});
	}
	vector<int> v;
	int ANS = 0;
	for(int i = 0; i < n; i++)
	{
		if(vis[i])
			continue;
		int mn = INF;
		int mx = -INF;
		dfs(i, -1);
		dfs2(i, -1, 0, mn, mx);
		ANS = max(ANS, mx);
		v.pb(mn);
		if(v.size() == 4)
		{
			sort(v.rbegin(), v.rend());
			v.pob();
		}
	}
	if(v.size() == 1)
		return ANS;
	ANS = max(ANS, L+v[0]+v[1]);
	if(v.size() < 3)
		return ANS;
	ANS = max(ANS, 2*L+v[1]+v[2]);
	return ANS;
}

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