Submission #526478

#	Time	Username	Problem	Language	Result	Execution time	Memory
526478		sliviu	Dreaming (IOI13_dreaming)	C++17	0 / 100	125 ms	26988 KiB

dreaming

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

using namespace std;
using pi = pair<int, int>;

pi operator +(pi a, int b) {
	return {a.first + b,a.second + b};
}

int travelTime(int n, int m, int cost, int A[], int B[], int T[]) {
	int ans = 0, t = 0;
	vector<int> seen(n), cn;
	vector<pi> dpu(n, {-0x3F3F3F3F,-0x3F3F3F3F}), dpb(n, {-0x3F3F3F3F,-0x3F3F3F3F});
	vector<vector<pi>> pref(n), suf(n);
	vector<pair<pi, 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]);
	}
	auto combine = [&](pi a, pi b) {
		pi ans;
		if (b > a)
			swap(a, b);
		ans.first = a.first;
		ans.second = max(a.second, b.first);
		return ans;
	};
	function<void(int, int)> dfs = [&](int node, int last) {
		cn.emplace_back(node);
		seen[node] = t;
		pref[node].emplace_back(-0x3F3F3F3F, -0x3F3F3F3F), suf[node].emplace_back(-0x3F3F3F3F, -0x3F3F3F3F);
		int leaf = 1;
		for (auto x : G[node])
			if (x.first != last) {
				leaf = 0;
				dfs(x.first, node);
				dpb[node] = combine(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);
			}
		if (leaf)
			dpb[node].first = 0;
		pref[node].emplace_back(-0x3F3F3F3F, -0x3F3F3F3F), suf[node].emplace_back(-0x3F3F3F3F, -0x3F3F3F3F);
		int s = pref[node].size();
		for (int i = 1; i <= s - 1; ++i)
			pref[node][i] = combine(pref[node][i], pref[node][i - 1]);
		for (int i = s - 2; i; --i)
			suf[node][i] = combine(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] = combine(combine(pref[node][ct - 1], suf[node][ct + 1]), dpu[node]) + x.second;
				//cout << x.first << ' ' << combine(pref[node][ct - 1], suf[node][ct + 1]).first << ' ' << dpu[x.first].first << '\n';
				dfs2(x.first, node);
				++ct;
			}
	};
	for (int i = 0; i < n; ++i)
		if (!seen[i]) {
			++t;
			cn.clear();
			dfs(i, -1);
			//dpu[i] = {0,-0x3F3F3F3F};
			dfs2(i, -1);
			pair<pi, int> ans = {{0x3F3F3F3F,0x3F3F3F3F}, 0};
			//cout << "ROOT : " << i << '\n';
			for (auto x : cn)
				//printf("%d : U %d D %d\n", x, dpu[x].first, dpb[x].first),
				ans = min(ans, {combine(dpu[x],dpb[x]),x});
			//cout << ans.first.first << ' ' <<  ans.first.second << ' ' << ans.second <<  '\n';
			cur.emplace_back(ans);
			//cout << ans.first.first << ' ' << ans.first.second << ' ' << ans.second << '\n';
		}
	pair<pi, int> node = cur.back();
	cur.pop_back();
	for (auto [c, n] : cur) {
		//cout << "ADD " << n << ' ' << node.second << '\n';
		G[n].emplace_back(node.second, cost);
		G[node.second].emplace_back(n, cost);
		if (c < node.first)
			node.first = combine(node.first, c + cost);
		else
			node.first = combine(node.first + cost, c), node.second = n;
	}
	//cout << node.first.first + node.first.second << '\n';
	return  node.first.first + node.first.second;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:12:6: warning: unused variable 'ans' [-Wunused-variable]
   12 |  int ans = 0, t = 0;
      |      ^~~

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