Submission #530541

#	Time	Username	Problem	Language	Result	Execution time	Memory
530541		buidangnguyen05	Dreaming (IOI13_dreaming)	C++14	0 / 100	49 ms	12108 KiB

dreaming

/* input

*/

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

typedef long long ll;
const int N = 1e5 + 10;
vector<pair<int, int>> adj[N];
vector<int> nodes;
int it, up[N], down[N][2], radius[N], res; bool dd[N];

void calc_down(int x, int par) {
	nodes.push_back(x); dd[x] = 1;
	for (pair<int, int> v : adj[x]) if (v.first != par) {
			int i, w; tie(i, w) = v;
			calc_down(i, x);
			if (down[i][0] + w > down[x][0]) {
				down[x][1] = down[x][0];
				down[x][0] = down[i][0] + w;
			}
			else if (down[i][0] + w > down[x][1]) down[x][1] = down[i][0] + w;
		}
}

void calc_up(int x, int par) {
	for (pair<int, int> v : adj[x]) if (v.first != par) {
			int i, w; tie(i, w) = v;
			up[i] = up[x] + w;
			if (down[i][0] + w == down[x][0]) up[i] = max(up[i], down[x][1] + w);
			else up[i] = max(up[i], down[x][0] + w);
			calc_up(i, x);
		}

	radius[it] = min(radius[it], max(up[x], down[x][0]));
	res = max(res, up[x] + down[x][0]);
}

int travelTime(int n, int m, int l, int x[], int y[], int w[]) {
	for (int i = 0; i < m; ++i) {
		++x[i]; ++y[i];
		adj[x[i]].push_back(make_pair(y[i], w[i]));
		adj[y[i]].push_back(make_pair(x[i], w[i]));
	}

	for (int i = 1; i <= n; ++i) if (!dd[i]) {
			++it; nodes.clear();
			calc_down(i, 0);
			calc_up(i, 0);
			radius[it] = 2e9;
		}

	sort(radius + 1, radius + it + 1, greater<int>());
	if (it > 1) res = max(res, radius[1] + radius[2] + l);
	if (it > 2) res = max(res, radius[2] + radius[3] + 2 * l);

	return res;
}

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