Submission #164828

#	Time	Username	Problem	Language	Result	Execution time	Memory
164828		Berted	Dreaming (IOI13_dreaming)	C++14	100 / 100	156 ms	13544 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define fst first
#define snd second
#define vpi vector<pii>
#define pub push_back

int n,m,l,dp[100001][2]={},mn = 1e9,rs = 0;
bool bt[100001]={};
priority_queue<int> pq;
vector<vpi> adj;

inline void dfs(int u,int p)
{
	bt[u] = 1;
	for (auto v:adj[u])
	{
		if (v.fst!=p)
		{
			dfs(v.fst,u);
			if (dp[v.fst][0] + v.snd > dp[u][0])
			{
				dp[u][1] = dp[u][0];
				dp[u][0] = dp[v.fst][0] + v.snd;
			}
			else if (dp[v.fst][0] + v.snd > dp[u][1])
			{
				dp[u][1] = dp[v.fst][0] + v.snd;
			}
		}
	}
}

inline void dfs2(int u,int p,int mx)
{
	mn = min(mn,max(mx,dp[u][0]));
	rs = max(rs,dp[u][0] + max(dp[u][1],mx));
	for (auto v:adj[u])
	{
		if (v.fst!=p)
		{
			bt[u] = 1;
			dfs2(v.fst,u,max(mx,(dp[u][0]==dp[v.fst][0] + v.snd)?dp[u][1]:dp[u][0]) + v.snd);
		}
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
	n = N;
	m = M;
	l = L;
	for (int i=0;i<n;i++) {adj.pub(vpi());}
	for (int i=0;i<m;i++)
	{
		adj[A[i]].pub({B[i],T[i]});
		adj[B[i]].pub({A[i],T[i]});
	}
	for (int i=0;i<n;i++)
	{
		if (!bt[i])
		{
			dfs(i,-1);
			dfs2(i,-1,0);
			//cout<<i<<" "<<mn<<"\n";
			pq.push(mn);
			mn = 1e9;
		}
	}
	if (pq.size()>2)
	{
	 	int a = pq.top();pq.pop();
	 	int b = pq.top();pq.pop();
	 	int c = pq.top();pq.pop();
	 	rs = max(rs,max(a + b + l,b + c + 2*l));
	}
	else if (pq.size()>1)
	{
		int a = pq.top();pq.pop();
	 	int b = pq.top();pq.pop();
	 	rs = max(rs,a + b + l);
	}
	return rs;
}

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