Submission #986353

#	Time	Username	Problem	Language	Result	Execution time	Memory
986353		Pyqe	Dreaming (IOI13_dreaming)	C++17	100 / 100	83 ms	24656 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long nn=0,mx,vtd[100069],bg[3],inf=1e18;
vector<pair<long long,long long>> al[100069];
pair<long long,long long> dp[100069];

void dfs(long long ky,long long x)
{
	long long i,sz=al[x].size(),l,w;
	
	vtd[x]=ky;
	dp[x]={0,x};
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		w=al[x][i].sc;
		if(vtd[l]!=ky)
		{
			dfs(ky,l);
			dp[x]=max(dp[x],{dp[l].fr+w,l});
		}
	}
}

int travelTime(int n,int m,int d,int ka[],int la[],int wg[])
{
	long long i,j,r,k,l,w,p,mn;
	
	for(i=0;i<m;i++)
	{
		k=ka[i];
		l=la[i];
		w=wg[i];
		al[k].push_back({l,w});
		al[l].push_back({k,w});
	}
	mx=-inf;
	for(i=0;i<3;i++)
	{
		bg[i]=-inf;
	}
	for(i=0;i<n;i++)
	{
		if(!vtd[i])
		{
			dfs(1,i);
			for(p=i;dp[p].sc!=p;p=dp[p].sc);
			dfs(2,p);
			w=dp[p].fr;
			mx=max(mx,w);
			mn=inf;
			for(;1;p=dp[p].sc)
			{
				mn=min(mn,max(dp[p].fr,w-dp[p].fr));
				if(dp[p].sc==p)
				{
					break;
				}
			}
			for(j=0;j<3;j++)
			{
				if(mn>bg[j])
				{
					for(r=2;r>j;r--)
					{
						bg[r]=bg[r-1];
					}
					bg[j]=mn;
					break;
				}
			}
		}
	}
	return max(mx,max(bg[0],bg[2]+d)+bg[1]+d);
}

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