Submission #520302

#	Time	Username	Problem	Language	Result	Execution time	Memory
520302		new_acc	Dreaming (IOI13_dreaming)	C++14	100 / 100	84 ms	13728 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=1e5+10;
vector<pair<int,int> >graf[N];
int naj1,naj2;
bool vis[N];
int oo[N];
int xdd;
void dfs(int v,int odl){
	if(vis[v]) return;
	vis[v]=1;
	if(odl>=naj1) naj1=odl,naj2=v;
	for(auto u:graf[v]) dfs(u.fi,odl+(ll)u.se);
}
void dfs2(int v,int o,int odl){
	if(odl>=naj1) naj1=odl,naj2=v;
	oo[v]=odl;
	for(auto u:graf[v]) {
		if(u.fi==o) continue;
		dfs2(u.fi,v,odl+(ll)u.se);
	}
}
void dfs3(int v,int o,int odl){
	oo[v]=max(oo[v],odl);
	xdd=min(xdd,oo[v]);
	for(auto u:graf[v]){
		if(u.fi==o) continue;
		dfs3(u.fi,v,odl+u.se);
	}
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
	for(int i=0;i<m;i++) a[i]++,b[i]++,graf[a[i]].push_back({b[i],t[i]}),graf[b[i]].push_back({a[i],t[i]});
	vector<int>v;
	int res=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			naj1=0,naj2=0;
			dfs(i,0);
			int g=naj2;
			naj1=0;
			dfs2(g,g,0);
			res=max(res,naj1);
			xdd=INT_MAX;
			dfs3(naj2,naj2,0);
			v.push_back(xdd);
		}
	}
	sort(v.begin(),v.end(),[](int a,int b){
		return a>b;
	});
	for(int i=1;i<=n;i++) vis[i]=0,oo[i]=0,graf[i].clear();
	if(v.size()==2) return max(v[0]+l+v[1],res);
	else{
		if(v.size()==1) return max(res,v[0]);
		else return max({v[0]+l+v[1],v[1]+l+l+v[2],res});
	}
}

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