Submission #147554

#	Time	Username	Problem	Language	Result	Execution time	Memory
147554		yum	Dreaming (IOI13_dreaming)	C++14	14 / 100	1049 ms	13688 KiB

dreaming

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

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<long long, long long> pl;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double EPS = 1e-6;
const int MAX_N = 1e5 + 5;

vector<pi> adjList[MAX_N];
bool found[MAX_N], found2[MAX_N];

pi BFS(int start) { //return {endpoint, longest path from start}
	queue<pi> q; //{node, dist}
	q.push({start, 0});
	pi ret; //answer
	found[start] = true;
	found2[start] = true;
	while (!q.empty()) {
		int u = q.front().ff, d = q.front().ss;
		if (d > ret.ss) ret = q.front();
		q.pop();
		for (pi edge: adjList[u]) {
			int v = edge.ff, w = edge.ss;
			if (!found2[v]) {
				found[v] = true;
				found2[v] = true;
				q.push({v, d + w});
			}
		}
	}
	return ret;
}

pair<int, pi> diameter(int start) { //returns {diameter, {endpoint, endpoint}}
	int end1 = BFS(start).ff;
	memset(found2, 0, sizeof found2);
	pi res = BFS(end1);
	return {res.ss, {end1, res.ff}};
}

int dia; //diameter
pi cen; //center - {min dist, node}
bool DFS(int u, int p, int end, int d) { //node, parent, second endpoint, distance from first endpoint to u
	if (u == end) return true;
	for (pi edge: adjList[u]) {
		int v = edge.ff, w = edge.ss;
		if (v == p) continue;
		if (DFS(v, u, end, d + w)) {
			if (max(d, dia - d) < cen.ff) {
				cen.ff = max(d, dia - d);
				cen.ss = u;
			}
			return true;
		}
	}
	return false;
}

pi center(int start) { //returns {center, maximum distance from center to other node}
	auto temp = diameter(start);
	dia = temp.ff;
	cen = {dia, -1};
	DFS(temp.ss.ff, -1, temp.ss.ss, 0);
	return {cen.ss, cen.ff};
}

int travelTime(int N, int M, int L, int* A, int* B, int* T) {
	for (int i = 0; i < M; ++i) {
		adjList[A[i]].push_back({B[i], T[i]});
		adjList[B[i]].push_back({A[i], T[i]});
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		if (!found[i]) {
			ans = max(ans, diameter(i).ff);
		}
	}
	memset(found, 0, sizeof found);
	memset(found2, 0, sizeof found2);
	vector<int> val;
	for (int i = 0; i < N; ++i) {
		if (!found[i]) val.push_back(center(i).ss);
	}
	sort(val.begin(), val.end());
	reverse(val.begin(), val.end());
	if (val.size() > 1) {
		ans = max(ans, L + val[0] + val[1]);
	}
	if (val.size() > 2) {
		ans = max(ans, 2 * L + val[1] + val[2]);
	}
	return ans;
}

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