Submission #1180910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180910		boclobanchat	Dreaming (IOI13_dreaming)	C++20	100 / 100	77 ms	31304 KiB

dreaming

#include"dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+5;
const int INF=1e9;
vector<ii> ds[MAXN];
bool ck[MAXN];
int dis[MAXN],dp[MAXN];
ii mx;
stack<int> st;
void fdia(int i,int pre)
{
	if(i==pre) dis[i]=0;
	mx=max(mx,{dis[i],i});
	for(auto v:ds[i]) if(v.fi!=pre&&v.fi!=i)
	{
		dis[v.fi]=dis[i]+v.se;
		fdia(v.fi,i);
	}
}
void fdis(int i,int pre)
{
	if(i==pre) dis[i]=0;
	mx=max(mx,{dis[i],i});
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		fdis(v.fi,i);
		dis[i]=max(dis[i],dis[v.fi]+v.se);
	}
}
void fmxdis(int i,int pre)
{
	st.push(i),ck[i]=true;
	if(i==pre) dp[i]=0;
	vector<int> pref,suff;
	pref.push_back(dp[i]);
	for(auto v:ds[i]) if(v.fi!=pre) pref.push_back(dis[v.fi]+v.se);
	pref.push_back(0),suff=pref;
	for(int j=1;j<pref.size();j++) pref[j]=max(pref[j],pref[j-1]);
	for(int j=pref.size()-2;j+1;j--) suff[j]=max(suff[j],suff[j+1]);
	int it=1;
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		dp[v.fi]=max(pref[it-1],suff[it+1])+v.se,it++;
		fmxdis(v.fi,i);
	}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
	for(int i=0;i<N-1;i++) ds[A[i]].push_back({B[i],T[i]}),ds[B[i]].push_back({A[i],T[i]});
	vector<ii> vi;
	for(int i=0;i<N;i++) if(!ck[i])
	{
		fdis(i,i);
		fmxdis(i,i);
		ii mn={INF,0};
		while(!st.empty())
		{
			int it=st.top();
			mn=min(mn,{max(dp[it],dis[it]),it}),st.pop();
		}
		vi.push_back(mn);
	}
	sort(vi.begin(),vi.end());
	int sz=vi.size();
	for(int i=0;i<sz-1;i++) ds[vi[i].se].push_back({vi[sz-1].se,L}),ds[vi[sz-1].se].push_back({vi[i].se,L});
	mx={-1,-1};
	fdia(0,0);
	int pos=mx.se;
	mx={-1,-1};
	fdia(pos,pos);
	return mx.fi;
}

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