oj.uz

Submission #526648

# Submission time Handle Problem Language Result Execution time Memory
526648 2022-02-15T20:22:17 Z sliviu Dreaming (IOI13_dreaming) C++17
32 / 100
 149 ms 31416 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 31416 KB Output is correct
2 Correct 128 ms 30816 KB Output is correct
3 Correct 81 ms 22920 KB Output is correct
4 Correct 13 ms 4940 KB Output is correct
5 Correct 11 ms 3436 KB Output is correct
6 Correct 24 ms 7328 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 52 ms 13752 KB Output is correct
9 Correct 76 ms 18892 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 114 ms 23648 KB Output is correct
12 Correct 149 ms 27548 KB Output is correct
13 Correct 2 ms 588 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 31416 KB Output is correct
2 Correct 128 ms 30816 KB Output is correct
3 Correct 81 ms 22920 KB Output is correct
4 Correct 13 ms 4940 KB Output is correct
5 Correct 11 ms 3436 KB Output is correct
6 Correct 24 ms 7328 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 52 ms 13752 KB Output is correct
9 Correct 76 ms 18892 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 114 ms 23648 KB Output is correct
12 Correct 149 ms 27548 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 23480 KB Output is correct
2 Correct 79 ms 23480 KB Output is correct
3 Correct 78 ms 23480 KB Output is correct
4 Correct 95 ms 23604 KB Output is correct
5 Correct 92 ms 23464 KB Output is correct
6 Correct 114 ms 24908 KB Output is correct
7 Correct 83 ms 24632 KB Output is correct
8 Correct 75 ms 23128 KB Output is correct
9 Correct 76 ms 22968 KB Output is correct
10 Correct 81 ms 24348 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 55 ms 23868 KB Output is correct
13 Correct 68 ms 23864 KB Output is correct
14 Correct 54 ms 23860 KB Output is correct
15 Correct 54 ms 23780 KB Output is correct
16 Correct 54 ms 23860 KB Output is correct
17 Correct 55 ms 23752 KB Output is correct
18 Correct 51 ms 23808 KB Output is correct
19 Correct 60 ms 23820 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 1 ms 300 KB Output is correct
22 Correct 2 ms 972 KB Output is correct
23 Correct 54 ms 23860 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 31416 KB Output is correct
2 Correct 128 ms 30816 KB Output is correct
3 Correct 81 ms 22920 KB Output is correct
4 Correct 13 ms 4940 KB Output is correct
5 Correct 11 ms 3436 KB Output is correct
6 Correct 24 ms 7328 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 52 ms 13752 KB Output is correct
9 Correct 76 ms 18892 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 114 ms 23648 KB Output is correct
12 Correct 149 ms 27548 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -