Submission #405080

#	Time	Username	Problem	Language	Result	Execution time	Memory
405080		Antekb	꿈 (IOI13_dreaming)	C++14	100 / 100	105 ms	18372 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=1e5+5;
const long long INF=1e18;
vector<pair<int, int>> E[N];
bool vis[N];
long long res=0;
long long dol[N], dolid[N], dol2[N];
void dfs(int v){
	vis[v]=1;
	dolid[v]=-1;
	dol[v]=dol2[v]=0;
	for(auto u:E[v]){
		if(!vis[u.st]){
			dfs(u.st);
			if(dol[u.st]+u.nd>dol[v]){
				dol2[v]=dol[v];
				dol[v]=dol[u.st]+u.nd;
				dolid[v]=u.st;
			}
			else if(dol[u.st]+u.nd>dol2[v])dol2[v]=dol[u.st]+u.nd;
		}
	}
	//cout<<v<<" "<<dol[v]<<" "<<dolid[v]<<" "<<dol2[v]<<"\n";
}
long long dfs2(int v, long long maks){
	long long ans=INF;
	vis[v]=1;
	for(auto u:E[v]){
		if(!vis[u.st]){
			if(u.st==dolid[v])ans=min(ans, dfs2(u.st, u.nd+max(maks, dol2[v])));
			else ans=min(ans, dfs2(u.st, u.nd+max(maks, dol[v])));
		}
	}
	ans=min(ans, max(maks, dol[v]));
	res=max(res, maks+dol[v]);
	return ans;
}
int travelTime(int n, int M, int L, int A[], int B[], int T[]) {
	for(int i=0; i<M; i++){
		E[A[i]].push_back({B[i], T[i]});
		E[B[i]].push_back({A[i], T[i]});
	}
	for(int i=0; i<n;i ++){
		if(!vis[i])dfs(i);
	}
	for(int i=0; i<n; i++)vis[i]=0;
	vector<long long > V;
	for(int i=0; i<n; i++){
		if(!vis[i])V.push_back(dfs2(i, 0));
	}
	sort(V.begin(), V.end());
	reverse(V.begin(), V.end());
	//cout<<V.size()<<"\n";
	//for(auto i:V)cout<<i<<" ";
//	cout<<"\n";
	if(V.size()>=2)res=max(res, V[0]+V[1]+L);
	if(V.size()>2)res=max(res, V[1]+V[2]+L+L);
	return 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