Submission #897404

#	Time	Username	Problem	Language	Result	Execution time	Memory
897404		Faisal_Saqib	Dreaming (IOI13_dreaming)	C++17	100 / 100	71 ms	19992 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std; 
const long long N=1e5+200;
vector<pair<long long,long long>> ma[N];
bool vis[N];
bool tp=0;
long long dp_down[N][2];
long long dp_up[N];
long long mxx[N];
long long n,m,l;
void dfs_down(long long x,long long p=-1)
{
	vis[x]=1;
	dp_down[x][0]=dp_down[x][1]=0;
	for(auto [w,y]:ma[x])
	{
		if(y!=p)
		{
			dfs_down(y,x);
			long long cur=dp_down[y][0]+w;
			if(dp_down[x][0]<cur)
			{
				dp_down[x][1]=dp_down[x][0];
				dp_down[x][0]=cur;
			}
			else if(dp_down[x][1]<cur)
			{
				dp_down[x][1]=cur;
			}
		}
	}
}
long long vertex=-1;
long long dist=1e18;
long long cp=-1;
void fill()
{
	for(int i=0;i<n;i++)
		dp_up[i]=0;
}
void dfs_up(long long x,long long p=-1)
{
	mxx[x]=max(dp_up[x],dp_down[x][0]);
	cp=max(cp,mxx[x]);
	if(mxx[x]<dist)
	{
		dist=mxx[x];
		vertex=x;
	}
	for(auto [w,y]:ma[x])
	{
		if(y!=p)
		{
			dp_up[y]=dp_up[x]+w;
			if(dp_down[x][0]==(dp_down[y][0]+w))
				dp_up[y]=max(dp_up[y],dp_down[x][1]+w);
			else
				dp_up[y]=max(dp_up[y],dp_down[x][0]+w);
			dfs_up(y,x);
		}
	}
}
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<m;i++)
	{
		ma[a[i]].push_back({t[i],b[i]});
		ma[b[i]].push_back({t[i],a[i]});
	}
	set<pair<long long,long long>> stp;
	for(int i=0;i<n;i++)
	{
		if(!vis[i]){
			vertex=-1;
			dist=1e18;
			dfs_down(i);
			dfs_up(i);
			stp.insert({dist,vertex});
		}
	}
	while(stp.size()>1)
	{
		auto lt=*(--end(stp));
		stp.erase((--end(stp)));
		auto ft=*(begin(stp));
		stp.erase((begin(stp)));
		// Merge them 
		ma[lt.second].push_back({l,ft.second});
		ma[ft.second].push_back({l,lt.second});
		vertex=lt.second;
		dist=max(ft.first+l,lt.first);
		// dfs_down(lt.second);
		// fill();
		// dfs_up(lt.second);
		stp.insert({dist,vertex});
	}
	cp=-1;
	tp=1;
	dfs_down(0);
	fill();
	dfs_up(0);
	// cout<<"adj\n";
	// for(int i=0;i<n;i++)
	// {
	// 	cout<<"For "<<i<<' ';
	// 	for(auto [j,p]:ma[i]){
	// 		cout<<p<<' ';
	// 	}
	// 	cout<<endl;
	// 	cout<<"a\n";
	// }
	return cp;
}

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