Submission #238287

#	Time	Username	Problem	Language	Result	Execution time	Memory
238287		kshitij_sodani	Dreaming (IOI13_dreaming)	C++17	100 / 100	115 ms	18680 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "dreaming.h"
int vis[100001];
vector<pair<int,int>> adj[100001];
int ss[100001];
int ma=1e9;
int ma2=0;
void dfs(int no,int par=-1){
	vis[no]=1;
	ss[no]=0;

	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		dfs(j.a,no);
		ss[no]=max(j.b+ss[j.a],ss[no]);
	}
//	cout<<no<<":"<<ss[no]<<endl;
}
void dfs2(int no,int par=-1,int prev=0){
	pair<int,int> aa={0,0};
	int bb=0;
	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		if(ss[j.a]+j.b>=aa.a){
			bb=aa.a;
			aa={ss[j.a]+j.b,j.a};
		}
		else if(ss[j.a]+j.b>=bb){
			bb=ss[j.a]+j.b;
		}
	}
/*	cout<<no<<endl;
	cout<<prev<<endl;
	cout<<aa.a<<":"<<aa.b<<":"<<bb<<endl;*/
	ma=min(ma,max(prev,aa.a));
	ma2=max(ma2,max(prev,aa.a));
	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		if(j.a==aa.b){
			dfs2(j.a,no,max(prev,bb)+j.b);
		}
		else{
			dfs2(j.a,no,max(prev,aa.a)+j.b);
		}
	}
}
int travelTime(int n,int m,int l,int aa[],int bb[],int tt[]){
	for(int i=0;i<m;i++){
		adj[aa[i]].pb({bb[i],tt[i]});
		adj[bb[i]].pb({aa[i],tt[i]});
	}
	vector<int> kk;
	vector<int> mm;
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			ma=1e9;
			ma2=0;
			dfs(i);
			dfs2(i);
			kk.pb(ma);
	//		cout<<i<<","<<ma<<","<<ma2<<endl;
			mm.pb(ma2);
		}
	}
	int ans=0;
	for(auto i:mm){
		ans=max(ans,i);
	}
	sort(kk.begin(),kk.end());
	reverse(kk.begin(),kk.end());
	if(kk.size()>1){
		ans=max(ans,kk[0]+kk[1]+l);
		if(kk.size()>2){
			ans=max(ans,kk[1]+kk[2]+l+l);
		}
	}
	return ans;


}
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,l;
	cin>>n>>m>>l;
	int aa[m];
	int bb[m];
	int tt[m];
	for(int i=0;i<m;i++){
		cin>>aa[i]>>bb[i]>>tt[i];
	}
	cout<<travelTime(n,m,l,aa,bb,tt)<<endl;



	return 0;
}
*/

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