oj.uz

Submission #305740

# Submission time Handle Problem Language Result Execution time Memory
305740 2020-09-23T22:19:45 Z Temmie Dreaming (IOI13_dreaming) C++17
18 / 100
 100 ms 12792 KB 
#include <bits/stdc++.h>
#include "dreaming.h"

std::vector <std::vector <std::pair <int, int>>> g;
std::vector <std::pair <int, int>> d1, d2;
std::vector <int> d;

std::vector <bool> vis;

void dfs1(int node, int par) {
	vis[node] = true;
	for (auto p : g[node]) if (p.first != par) {
		int x = p.first, w = p.second;
		dfs1(x, node);
		d2[node] = std::max(d2[node], { d1[x].first + w, x });
		if (d2[node] > d1[node]) std::swap(d1[node], d2[node]);
	}
}

std::vector <int> nows;
void dfs2(int node, int par, int dist) {
	vis[node] = true;
	nows.push_back(node);
	d[node] = std::max(d1[node].first, dist);
	for (auto p : g[node]) if (p.first != par) {
		int x = p.first, w = p.second;
		if (x == d1[node].second) dfs2(x, node, std::max(d2[node].first, dist) + w);
		else dfs2(x, node, d[node] + w);
	}
}

bool comp(const int& a, const int& b) {
	return d[a] < d[b];
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	g.resize(n);
	d1.resize(n);
	d2.resize(n);
	d.resize(n);
	for (int i = 0; i < m; i++) {
		g[a[i]].push_back({ b[i], t[i] });
		g[b[i]].push_back({ a[i], t[i] });
	}
	vis.resize(n, false);
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			dfs1(i, -1);
		}
	}
	vis.clear();
	vis.resize(n, false);
	std::vector <int> ws;
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			dfs2(i, -1, 0);
			std::sort(nows.begin(), nows.end(), comp);
			ws.push_back(d[nows[0]]);
			nows.clear();
		}
	}
	std::sort(ws.rbegin(), ws.rend());
	if (ws.size() == size_t(1)) return ws[0];
	if (ws.size() == size_t(2)) return ws[0] + ws[1] + l;
	return std::max(ws[0] + ws[1] + l, ws[1] + ws[2] + l + l);
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 12792 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 39 ms 7036 KB Output is correct
2 Correct 36 ms 7160 KB Output is correct
3 Correct 35 ms 7544 KB Output is correct
4 Correct 36 ms 7544 KB Output is correct
5 Correct 38 ms 7544 KB Output is correct
6 Correct 44 ms 8312 KB Output is correct
7 Correct 37 ms 7808 KB Output is correct
8 Correct 38 ms 7544 KB Output is correct
9 Correct 37 ms 7320 KB Output is correct
10 Correct 36 ms 7800 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 9 ms 5368 KB Output is correct
13 Correct 9 ms 5372 KB Output is correct
14 Correct 9 ms 5372 KB Output is correct
15 Correct 10 ms 5372 KB Output is correct
16 Correct 8 ms 5372 KB Output is correct
17 Correct 8 ms 5372 KB Output is correct
18 Correct 9 ms 5372 KB Output is correct
19 Correct 8 ms 5372 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 9 ms 5372 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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