Submission #1170408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170408		rayan_bd	Dreaming (IOI13_dreaming)	C++20	47 / 100	58 ms	18828 KiB

dreaming

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

using namespace std;

#define ll long long
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second

const int INF = 2e9;
const int mxN = 1e5 + 5000;

vector<pair<int,int>> adj[mxN];
int down_dp[mxN],up_dp[mxN],dp[mxN],vis[mxN],cost1=0,cost2=0,grp=1;
vector<int> group_max(mxN,INF),group_max_node(mxN,0);

void dfs(int u,int par){
	vis[u]=grp;
	for(auto it:adj[u]){
		 if(it.fi==par) continue;
		 dfs(it.fi,u);
		 down_dp[u]=max(down_dp[u],down_dp[it.fi]+it.se);
	}
}

void reroot(int u,int par){
	int c[2]; pair<int,int> p;
	p.fi=p.se=-1;
	c[0]=c[1]=0;
	dp[u]=max(dp[u],down_dp[u]);
	for(auto it:adj[u]){
		if(it.fi!=par){
			if(p.fi==-1) p.fi=it.fi,c[0]=it.se;
			else if(down_dp[p.fi]+c[0]<down_dp[it.fi]+it.se){
				swap(p.fi,p.se);
				swap(c[0],c[1]);
				c[0]=it.se;
				p.fi=it.fi;
			}else if(down_dp[p.se]+c[1]<down_dp[it.fi]+it.se){
				p.se=it.fi;
				c[1]=it.se;
			}
		}
	}
	for(auto it:adj[u]){
		if(it.fi^par){
			up_dp[it.fi]=up_dp[u]+it.se;
			if(it.fi==p.fi&&p.fi==-1) up_dp[it.fi]=0;
			else if(it.fi==p.fi) up_dp[it.fi]=max(up_dp[it.fi],down_dp[p.se]+c[1]+it.se);
			else up_dp[it.fi]=max(up_dp[it.fi],down_dp[p.fi]+c[0]+it.se);
			dp[it.fi]=max(up_dp[it.fi],down_dp[it.fi]);
			reroot(it.fi,u);
		}
	}
	cost1=max(cost1,dp[u]);
}

pair<int,int> max_dist(int u,int par,int w){
	pair<int,int> ans={w,u};
	for(auto it:adj[u]){
		if(it.fi!=par){	
			ans=max(ans,max_dist(it.fi,u,w+it.se));
		}
	}
	return ans;
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
	for(int i=0;i<M;++i){
		adj[A[i]].pb({B[i],T[i]});
		adj[B[i]].pb({A[i],T[i]});
	}

	for(int i=0;i<N;++i){
		if(vis[i]==0){
			dfs(i,-1);
			reroot(i,-1);
			++grp;
		}
	}

	for(int i=0;i<N;++i){
		if(group_max[vis[i]]>dp[i]){
			group_max[vis[i]]=dp[i];
			group_max_node[vis[i]]=i;
		}
	}

	for(int i=2;i<grp;++i){
		adj[group_max_node[i-1]].pb({group_max_node[i],L});
		adj[group_max_node[i]].pb({group_max_node[i-1],L});
	}


	pair<int,int> p1=max_dist(0,-1,0);
	pair<int,int> p2=max_dist(p1.se,-1,0);

	return max(cost1,group_max[1]+group_max[2]+L);
}

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