oj.uz

Submission #147555

# Submission time Handle Problem Language Result Execution time Memory
147555 2019-08-30T03:58:54 Z yum Dreaming (IOI13_dreaming) C++14
14 / 100
 1000 ms 13944 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pi;
typedef pair<long long, long long> pl;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double EPS = 1e-6;
const int MAX_N = 1e5 + 5;

vector<pi> adjList[MAX_N];
bool found[MAX_N], found2[MAX_N];

pi BFS(ll start) { //return {endpoint, longest path from start}
	queue<pi> q; //{node, dist}
	q.push({start, 0});
	pi ret; //answer
	found[start] = true;
	found2[start] = true;
	while (!q.empty()) {
		ll u = q.front().ff, d = q.front().ss;
		if (d > ret.ss) ret = q.front();
		q.pop();
		for (pi edge: adjList[u]) {
			ll v = edge.ff, w = edge.ss;
			if (!found2[v]) {
				found[v] = true;
				found2[v] = true;
				q.push({v, d + w});
			}
		}
	}
	return ret;
}

pair<ll, pi> diameter(ll start) { //returns {diameter, {endpoint, endpoint}}
	ll end1 = BFS(start).ff;
	memset(found2, 0, sizeof found2);
	pi res = BFS(end1);
	return {res.ss, {end1, res.ff}};
}

ll dia; //diameter
pi cen; //center - {min dist, node}
bool DFS(ll u, ll p, ll end, ll d) { //node, parent, second endpoint, distance from first endpoint to u
	if (u == end) return true;
	for (pi edge: adjList[u]) {
		ll v = edge.ff, w = edge.ss;
		if (v == p) continue;
		if (DFS(v, u, end, d + w)) {
			if (max(d, dia - d) < cen.ff) {
				cen.ff = max(d, dia - d);
				cen.ss = u;
			}
			return true;
		}
	}
	return false;
}

pi center(ll start) { //returns {center, maximum distance from center to other node}
	auto temp = diameter(start);
	dia = temp.ff;
	cen = {dia, -1};
	DFS(temp.ss.ff, -1, temp.ss.ss, 0);
	return {cen.ss, cen.ff};
}

int travelTime(int N, int M, int L, int* A, int* B, int* T) {
	for (ll i = 0; i < M; ++i) {
		adjList[A[i]].push_back({B[i], T[i]});
		adjList[B[i]].push_back({A[i], T[i]});
	}
	ll ans = 0;
	for (ll i = 0; i < N; ++i) {
		if (!found[i]) {
			ans = max(ans, diameter(i).ff);
		}
	}
	memset(found, 0, sizeof found);
	memset(found2, 0, sizeof found2);
	vector<ll> val;
	for (ll i = 0; i < N; ++i) {
		if (!found[i]) val.push_back(center(i).ss);
	}
	sort(val.begin(), val.end());
	reverse(val.begin(), val.end());
	if (val.size() > 1) {
		ans = max(ans, L + val[0] + val[1]);
	}
	if (val.size() > 2) {
		ans = max(ans, 2 * L + val[1] + val[2]);
	}
	return ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13944 KB Output is correct
2 Correct 105 ms 13944 KB Output is correct
3 Correct 65 ms 10360 KB Output is correct
4 Correct 15 ms 4472 KB Output is correct
5 Correct 13 ms 3832 KB Output is correct
6 Correct 24 ms 5496 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 46 ms 7032 KB Output is correct
9 Correct 59 ms 8628 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 88 ms 10360 KB Output is correct
12 Correct 113 ms 12276 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13944 KB Output is correct
2 Correct 105 ms 13944 KB Output is correct
3 Correct 65 ms 10360 KB Output is correct
4 Correct 15 ms 4472 KB Output is correct
5 Correct 13 ms 3832 KB Output is correct
6 Correct 24 ms 5496 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 46 ms 7032 KB Output is correct
9 Correct 59 ms 8628 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 88 ms 10360 KB Output is correct
12 Correct 113 ms 12276 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Incorrect 4 ms 2936 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13944 KB Output is correct
2 Correct 105 ms 13944 KB Output is correct
3 Correct 65 ms 10360 KB Output is correct
4 Correct 15 ms 4472 KB Output is correct
5 Correct 13 ms 3832 KB Output is correct
6 Correct 24 ms 5496 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 46 ms 7032 KB Output is correct
9 Correct 59 ms 8628 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 88 ms 10360 KB Output is correct
12 Correct 113 ms 12276 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Incorrect 4 ms 2936 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 5872 KB Output is correct
2 Correct 693 ms 5904 KB Output is correct
3 Correct 692 ms 6028 KB Output is correct
4 Correct 695 ms 5784 KB Output is correct
5 Correct 689 ms 5876 KB Output is correct
6 Correct 747 ms 6536 KB Output is correct
7 Correct 718 ms 6288 KB Output is correct
8 Correct 687 ms 6012 KB Output is correct
9 Correct 660 ms 5876 KB Output is correct
10 Correct 751 ms 5960 KB Output is correct
11 Correct 5 ms 2940 KB Output is correct
12 Execution timed out 1064 ms 4080 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13944 KB Output is correct
2 Correct 105 ms 13944 KB Output is correct
3 Correct 65 ms 10360 KB Output is correct
4 Correct 15 ms 4472 KB Output is correct
5 Correct 13 ms 3832 KB Output is correct
6 Correct 24 ms 5496 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 46 ms 7032 KB Output is correct
9 Correct 59 ms 8628 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 88 ms 10360 KB Output is correct
12 Correct 113 ms 12276 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Correct 7 ms 2936 KB Output is correct
15 Correct 9 ms 3064 KB Output is correct
16 Incorrect 11 ms 3064 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13944 KB Output is correct
2 Correct 105 ms 13944 KB Output is correct
3 Correct 65 ms 10360 KB Output is correct
4 Correct 15 ms 4472 KB Output is correct
5 Correct 13 ms 3832 KB Output is correct
6 Correct 24 ms 5496 KB Output is correct
7 Correct 4 ms 2936 KB Output is correct
8 Correct 46 ms 7032 KB Output is correct
9 Correct 59 ms 8628 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 88 ms 10360 KB Output is correct
12 Correct 113 ms 12276 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Incorrect 4 ms 2936 KB Output isn't correct
15 Halted 0 ms 0 KB -