oj.uz

Submission #421694

# Submission time Handle Problem Language Result Execution time Memory
421694 2021-06-09T11:01:17 Z SuhaibSawalha1 Dreaming (IOI13_dreaming) C++17
14 / 100
 80 ms 9520 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int, 2>>> adj;
vector<int> dist, nodes;
int n;

array<int, 2> bfs (int u, bool f) {
	queue<array<int, 3>> q {{{u, 0}}};
	array<int, 2> MX {0, u};
	int v = 0;
	while (q.size()) {
		++v;
		u = q.front()[0];
		int d = q.front()[1];
		int p = q.front()[2];
		q.pop();
		if (f) {
			nodes.push_back(u);
			dist[u] = max(dist[u], d);
		}
		MX = max(MX, {d, u});
		for (auto &v : adj[u]) {
			if (v[0] != p) {
				q.push({v[0], d + v[1], u});
			}
		}
	}
	return MX;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N;
	adj.resize(N);
	dist.resize(N);
	for (int i = 0; i < M; ++i) {
		adj[A[i]].push_back({B[i], T[i]});
		adj[B[i]].push_back({A[i], T[i]});
	}
	vector<array<int, 2>> cmp;
	for (int i = 0; i < N; ++i) {
		if (!dist[i]) {
			int a = bfs(i, 0)[1];
			nodes.clear();
			bfs(bfs(a, 1)[1], 1);
			array<int, 2> mn = {(int)2e9, (int)2e9};
			for (int u : nodes) {
				mn = min(mn, {dist[u], u});
			}
			cmp.push_back(mn);
		}
	}
	int mx = (*max_element(cmp.begin(), cmp.end()))[1];
	for (auto &e : cmp) {
		if (e[1] != mx) {
			adj[e[1]].push_back({mx, L});
			adj[mx].push_back({e[1], L});
		}
	}
	return bfs(bfs(0, 0)[1], 0)[0];
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8768 KB Output is correct
2 Correct 53 ms 8996 KB Output is correct
3 Correct 38 ms 6052 KB Output is correct
4 Correct 8 ms 1612 KB Output is correct
5 Correct 6 ms 1244 KB Output is correct
6 Correct 13 ms 2340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 27 ms 3920 KB Output is correct
9 Correct 36 ms 5052 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 54 ms 6920 KB Output is correct
12 Correct 80 ms 8156 KB Output is correct
13 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Incorrect 1 ms 204 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8768 KB Output is correct
2 Correct 53 ms 8996 KB Output is correct
3 Correct 38 ms 6052 KB Output is correct
4 Correct 8 ms 1612 KB Output is correct
5 Correct 6 ms 1244 KB Output is correct
6 Correct 13 ms 2340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 27 ms 3920 KB Output is correct
9 Correct 36 ms 5052 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 54 ms 6920 KB Output is correct
12 Correct 80 ms 8156 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 304 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 300 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Incorrect 1 ms 204 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9068 KB Output is correct
2 Correct 66 ms 8356 KB Output is correct
3 Correct 68 ms 8244 KB Output is correct
4 Correct 68 ms 8280 KB Output is correct
5 Correct 63 ms 8296 KB Output is correct
6 Correct 70 ms 8836 KB Output is correct
7 Correct 67 ms 9520 KB Output is correct
8 Correct 69 ms 8952 KB Output is correct
9 Correct 66 ms 8140 KB Output is correct
10 Correct 70 ms 8588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 56 ms 8940 KB Output is correct
13 Correct 57 ms 8876 KB Output is correct
14 Correct 57 ms 8888 KB Output is correct
15 Correct 56 ms 8856 KB Output is correct
16 Correct 59 ms 8888 KB Output is correct
17 Correct 67 ms 9060 KB Output is correct
18 Correct 66 ms 8828 KB Output is correct
19 Correct 58 ms 8880 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Incorrect 1 ms 204 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8768 KB Output is correct
2 Correct 53 ms 8996 KB Output is correct
3 Correct 38 ms 6052 KB Output is correct
4 Correct 8 ms 1612 KB Output is correct
5 Correct 6 ms 1244 KB Output is correct
6 Correct 13 ms 2340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 27 ms 3920 KB Output is correct
9 Correct 36 ms 5052 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 54 ms 6920 KB Output is correct
12 Correct 80 ms 8156 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 304 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 300 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Incorrect 1 ms 204 KB Output isn't correct
29 Halted 0 ms 0 KB -