Submission #383493

#	Time	Username	Problem	Language	Result	Execution time	Memory
383493		alireza_kaviani	Dreaming (IOI13_dreaming)	C++11	100 / 100	108 ms	18048 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

typedef pair<int, int> pii;

#define X			first
#define Y			second
#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int(x.size())

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int mark[MAXN] , dpDown[MAXN] , dpUp[MAXN];
vector<int> vec;
vector<pii> adj[MAXN];

void DFSDown(int v , int p = -1){
	mark[v] = 1;
	vec.push_back(v);
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		DFSDown(u , v);
		dpDown[v] = max(dpDown[v] , dpDown[u] + w);
	}
}

void DFSUp(int v , int p = -1){
	int mx = 0;
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		dpUp[u] = max(dpUp[v] , mx) + w;
		mx = max(mx , dpDown[u] + w);
	}
	reverse(all(adj[v])); mx = 0;
	for(pii i : adj[v]){
		int u = i.X , w = i.Y;
		if(u == p)	continue;
		dpUp[u] = max(dpUp[u] , max(dpUp[v] , mx) + w);
		mx = max(mx , dpDown[u] + w);
//		cout << v << ' ' << u << ' ' << mx << endl;
		DFSUp(u , v);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0 ; i < M ; i++){
		adj[A[i]].push_back({B[i] , T[i]});
		adj[B[i]].push_back({A[i] , T[i]});
	}
	int ans = 0;
	vector<int> v;
	for(int i = 0 ; i < N ; i++){
		if(mark[i])	continue;
		vec = {};
		DFSDown(i);
		DFSUp(i);
		int R = MOD * 2;
		for(int j : vec){
			int cur = max(dpDown[j] , dpUp[j]);
			R = min(R , cur);
			ans = max(ans , cur);
		}
		v.push_back(R);
//		cout << R << endl;
	}
	sort(all(v) , greater<int>());
	if(SZ(v) >= 2)	ans = max(ans , v[0] + v[1] + L);
	if(SZ(v) >= 3)	ans = max(ans , v[1] + v[2] + L + L);
	return ans;
	//cout << N << endl;
	//for(int i = 0 ; i < N ; i++)	cout << i << ' ' << dpDown[i] << ' ' << dpUp[i] << endl;
}

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