Submission #164799

#	Time	Username	Problem	Language	Result	Execution time	Memory
164799		Berted	Dreaming (IOI13_dreaming)	C++14	47 / 100	108 ms	13536 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,vector<int>,greater<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;
		}
	}
	while (pq.size()>1)
	{
		int v1 = pq.top();pq.pop();
		int v2 = pq.top();pq.pop();
		pq.push(min(max(v1,v2+l),max(v2,v1+l)));
		rs = max(rs,v1+v2+l);
	}
	return rs;
}

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