oj.uz

Submission #304151

# Submission time Handle Problem Language Result Execution time Memory
304151 2020-09-21T03:40:22 Z Fischer Dreaming (IOI13_dreaming) C++14
18 / 100
 61 ms 11384 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int maxn = 1e5 + 10;
vector<pair<int, int>> g[maxn];
pair<int, int> len[maxn];
bool vis[maxn];
int arr[maxn];
int k = 0;

void add(int x, int t) {
	if (t >= len[x].first) {
		len[x].second = len[x].first;
		len[x].first = t;
	} else {
		len[x].second = max(len[x].second, t);
	}
}

void dfs(int x, int p) {
	vis[x] = 1;
	len[x] = {0, 0};
	for (auto e : g[x]) {
		if (e.first == p) continue;
		dfs(e.first, x);
		add(x, len[e.first].first+e.second);
	}
}

int dfs_reroot(int x, int p, int r) {
	if (p != -1) {
		if (len[p].first == len[x].first+r) {
			add(x, len[p].second+r);
		} else {
			add(x, len[p].first+r);
		}
	}
	int ans = len[x].first;
	for (auto e : g[x]) {
		if (e.first == p) continue;
		ans = max(ans, dfs_reroot(e.first, x, e.second));
	}
	return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i=0; i<N; ++i) g[i].clear(), vis[i] = 0;
	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]);
	}
	for (int i=0; i<N; ++i) {
		if (vis[i]) continue;
		dfs(i, -1);
		arr[k++] = dfs_reroot(i, -1, 0);
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) ans = max(ans, len[i].first + len[i].second);
	sort(arr, arr+k, greater<int>());
	if (k >= 2) ans = max(ans, arr[0] + arr[1] + L);
	if (k >= 3) ans = max(ans, arr[1] + arr[2] + 2 * L);
	return ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6016 KB Output is correct
2 Correct 27 ms 6528 KB Output is correct
3 Correct 27 ms 6528 KB Output is correct
4 Correct 26 ms 6528 KB Output is correct
5 Correct 26 ms 6528 KB Output is correct
6 Correct 28 ms 6784 KB Output is correct
7 Correct 27 ms 6656 KB Output is correct
8 Correct 25 ms 6400 KB Output is correct
9 Correct 25 ms 6400 KB Output is correct
10 Correct 26 ms 6648 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 6 ms 3968 KB Output is correct
13 Correct 5 ms 3968 KB Output is correct
14 Correct 5 ms 3968 KB Output is correct
15 Correct 5 ms 3968 KB Output is correct
16 Correct 5 ms 3968 KB Output is correct
17 Correct 5 ms 3968 KB Output is correct
18 Correct 6 ms 3968 KB Output is correct
19 Correct 5 ms 3968 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 2 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct
23 Correct 5 ms 3968 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -