Submission #134837

#	Time	Username	Problem	Language	Result	Execution time	Memory
134837		mirbek01	Dreaming (IOI13_dreaming)	C++11	100 / 100	140 ms	25452 KiB

dreaming

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

using namespace std;

const int N = 1e5 + 3;

int u[N], dw[N], up[N], ans, mx;
vector < pair <int, int> >  g[N];

void dfs(int v, int pr){
	u[v] = 1;
	int mx1 = 0, mx2 = 0;
	for(int i = 0; i < (int)g[v].size(); i ++){
		int to = g[v][i].first, len = g[v][i].second;
		if(to == pr)
			continue;
		dfs(to, v);
		dw[v] = max(dw[v], dw[to] + len); 
		if(mx1 < dw[to] + len)
			mx2 = mx1, mx1 = dw[to] + len;
		else 
			mx2 = max(mx2, dw[to] + len);
	} 
	ans = max(ans, mx1 + mx2);
}
	
void dfs1(int v, int pr){
	mx = min(mx, max(up[v], dw[v]));
	vector < pair <int, int> > vec;
	for(int i = 0; i < (int)g[v].size(); i ++){
		int to = g[v][i].first, len = g[v][i].second;
		if(to == pr) continue;
		vec.push_back( {dw[to] + len, to} );
	}
	sort(vec.rbegin(), vec.rend());
	for(int i = 0; i < (int)g[v].size(); i ++){
		int to = g[v][i].first, len = g[v][i].second;
		if(to == pr)
			continue;
		up[to] = max(up[to], up[v] + len);
		if(to == vec[0].second){
			if((int)vec.size() > 1)
				up[to] = max(up[to], vec[1].first + len);
		} else {
			up[to] = max(up[to], vec[0].first + len);
		} 
		dfs1(to, v);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i = 0; i < M; i ++){
		int u = A[i], v = B[i], w = T[i];
		g[u].push_back( {v, w} );
		g[v].push_back( {u, w} );
	}

	vector <int> vec;
	
	for(int i = 0; i < N; i ++){
		if(!u[i]){
			mx = 2e9;
			dfs(i, -1);
			dfs1(i, -1);
			vec.push_back(mx);
		}
	}
	
	sort(vec.rbegin(), vec.rend());
	
	if((int)vec.size() > 1)
		ans = max(ans, vec[0] + vec[1] + L);
	if((int)vec.size() > 2)
		ans = max(ans, vec[1] + vec[2] + L + L);
	return ans;
}

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