Submission #526648

#	Time	Username	Problem	Language	Result	Execution time	Memory
526648		sliviu	Dreaming (IOI13_dreaming)	C++17	32 / 100	149 ms	31416 KiB

dreaming

#include <dreaming.h>
#include <bits/stdc++.h>
#define int long long

using namespace std;

int32_t travelTime(int32_t n, int32_t m, int32_t cost, int32_t A[], int32_t B[], int32_t T[]) {
	int ans = 0, t = 0;
	vector<int> seen(n), dpu(n), dpb(n), cn;
	vector<vector<int>> pref(n), suf(n);
	deque<pair<int, int>> cur;
	vector<vector<pair<int, int>>> G(n);
	for (int i = 0; i < m; ++i) {
		G[A[i]].emplace_back(B[i], T[i]);
		G[B[i]].emplace_back(A[i], T[i]);
	}
	function<void(int, int)> dfs1 = [&](int node, int last) {
		cn.emplace_back(node);
		seen[node] = t;
		pref[node].emplace_back(0), suf[node].emplace_back(0);
		for (auto x : G[node])
			if (x.first != last) {
				dfs1(x.first, node);
				dpb[node] = max(dpb[node], dpb[x.first] + x.second);
				pref[node].emplace_back(dpb[x.first] + x.second);
				suf[node].emplace_back(dpb[x.first] + x.second);
			}
		pref[node].emplace_back(0), suf[node].emplace_back(0);
		int s = pref[node].size() - 1;
		for (int i = 1; i <= s; ++i)
			pref[node][i] = max(pref[node][i], pref[node][i - 1]);
		for (int i = s; i; --i)
			suf[node][i] = max(suf[node][i], suf[node][i + 1]);
	};
	function<void(int, int)> dfs2 = [&](int node, int last) {
		int ct = 1;
		for (auto x : G[node])
			if (x.first != last) {
				dpu[x.first] = x.second + max(max(pref[node][ct - 1], suf[node][ct + 1]), dpu[node]);
				dfs2(x.first, node);
				++ct;
			}
	};
	for (int i = 0; i < n; ++i)
		if (!seen[i]) {
			++t;
			cn.clear();
			dfs1(i, -1);
			dfs2(i, -1);
			pair<int, int> ans = {INT_MAX, 0};
			for (auto x : cn)
				ans = min(ans, {max(dpu[x],dpb[x]),x});
			cur.emplace_back(ans);
		}
	sort(cur.begin(), cur.end());
	reverse(cur.begin(), cur.end());
	pair<int, int> node = cur.front();
	cur.pop_front();
	for (auto [c, n] : cur) {
		G[n].emplace_back(node.second, cost);
		G[node.second].emplace_back(n, cost);
	}
	vector<int> dp1(n), dp2(n);
	function<void(int, int)> dfs = [&](int node, int last) {
		for (auto x : G[node])
			if (x.first != last) {
				dfs(x.first, node);
				int cost = dp1[x.first] + x.second;
				if (cost >= dp1[node])
					dp2[node] = dp1[node], dp1[node] = cost;
				else if (cost > dp2[node])
					dp2[node] = cost;
			}
	};
	dfs(0, -1);
	for (int i = 0; i < n; ++i)
		ans = max(ans, dp1[i] + dp2[i]);
	return ans;
}

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