Submission #221811

#	Time	Username	Problem	Language	Result	Execution time	Memory
221811		patrikpavic2	Dreaming (IOI13_dreaming)	C++17	100 / 100	104 ms	17528 KiB

dreaming

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  dreaming
* score: 100.0
* date:  2019-06-27 09:30:59.412917
*/
#include "dreaming.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < pii > vp;

const int N = 1e5 + 500;
const int INF = 0x3f3f3f3f;

int d[N], u[N], dp[N], min_sol;
vp v[N];

void calc_d(int x,int lst){
	for(pii y : v[x]){
		if(y.X == lst) continue;
		calc_d(y.X, x);
		d[x] = max(d[y.X] + y.Y, d[x]);
	}
}

void calc(int x,int lst){
	int dos = u[x];
	for(pii y : v[x]){
		if(y.X == lst) continue;
		u[y.X] = max(u[y.X],y.Y + dos);
		dos = max(dos, d[y.X] + y.Y);
	}
	reverse(v[x].begin(), v[x].end());
	dos = 0;
	for(pii y : v[x]){
		if(y.X == lst) continue;
		u[y.X] = max(u[y.X],y.Y + dos);
		dos = max(dos, d[y.X] + y.Y);
	}
	reverse(v[x].begin(), v[x].end());
	dp[x] = min(max(u[x], d[x]), dp[x]);
	min_sol = max(min_sol, d[x] + u[x]);
	for(pii y : v[x]){
		if(y.X == lst) continue;
		calc(y.X, x);
		dp[x] = min(dp[x], dp[y.X]);
	}
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i = 0;i < M;i++){
		v[A[i]].PB({B[i], T[i]});
		v[B[i]].PB({A[i], T[i]});
	}    
	memset(dp, INF, sizeof(dp));
	vi f;
	for(int i = 0;i < N;i++){
		if(dp[i] != INF) continue;
		calc_d(i, i); calc(i, i);
		f.PB(dp[i]);
	}
	sort(f.rbegin(), f.rend());
	if(f.size() == 1) return max(f[0], min_sol);
	else if(f.size() == 2) return max(f[0] + f[1] + L, min_sol);
	return max(max(f[0] + f[1] + L, f[1] + f[2] + 2 * L), min_sol);
}

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