Submission #222852

#	Time	Username	Problem	Language	Result	Execution time	Memory
222852		staniewzki	Dreaming (IOI13_dreaming)	C++17	18 / 100	87 ms	17392 KiB

dreaming

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

#include "dreaming.h"

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	vector<vector<PII>> adj(N);
	REP(i, M) {
		adj[A[i]].emplace_back(B[i], T[i]);
		adj[B[i]].emplace_back(A[i], T[i]);
	}

	vector<int> dst(N, -1), component;
	function<void(int, bool)> get_dst = [&](int v, bool get_comp) {
		if(get_comp) component.emplace_back(v);
		if(dst[v] == -1) dst[v] = 0;
		for(auto &[u, w] : adj[v]) {
			if(dst[u] == -1) {
				dst[u] = dst[v] + w;
				get_dst(u, get_comp);
			}
		}
	};

	auto clear_dst = [&]() {
		for(int i : component)
			dst[i] = -1;
	};

	int inf = (int) 1e9;
	vector<int> cen(N), q = {-inf, -inf};
	REP(i, N) if(dst[i] == -1) {
		auto get_far = [&](int x) {
			clear_dst();
			get_dst(x, false);
			PII best = {-1, -1};
			for(int j : component) 
				best = max(best, {dst[j], j});
			return best.ND;
		};

		auto update_cen = [&]() {
			int ret = inf;
			for(int j : component) {
				cen[j] = max(cen[j], dst[j]);
				ret = min(ret, cen[j]);
			}
			return ret;
		};

		get_dst(i, true);

		int a = get_far(i);
		int b = get_far(a);
		update_cen();
		get_far(b);
		q.emplace_back(update_cen());

		component.clear();
	}

	sort(q.rbegin(), q.rend());
	return max({q[0], q[0] + L + q[1], q[1] + 2 * L + q[2]});
}

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