oj.uz

Submission #147554

# Submission time Handle Problem Language Result Execution time Memory
147554 2019-08-30T03:55:21 Z yum Dreaming (IOI13_dreaming) C++14
14 / 100
 1000 ms 13688 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<int, int> 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(int 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()) {
		int u = q.front().ff, d = q.front().ss;
		if (d > ret.ss) ret = q.front();
		q.pop();
		for (pi edge: adjList[u]) {
			int v = edge.ff, w = edge.ss;
			if (!found2[v]) {
				found[v] = true;
				found2[v] = true;
				q.push({v, d + w});
			}
		}
	}
	return ret;
}

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

int dia; //diameter
pi cen; //center - {min dist, node}
bool DFS(int u, int p, int end, int d) { //node, parent, second endpoint, distance from first endpoint to u
	if (u == end) return true;
	for (pi edge: adjList[u]) {
		int 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(int 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 (int i = 0; i < M; ++i) {
		adjList[A[i]].push_back({B[i], T[i]});
		adjList[B[i]].push_back({A[i], T[i]});
	}
	int ans = 0;
	for (int 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<int> val;
	for (int 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 80 ms 13688 KB Output is correct
2 Correct 85 ms 13688 KB Output is correct
3 Correct 55 ms 10104 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3704 KB Output is correct
6 Correct 23 ms 5240 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 41 ms 6648 KB Output is correct
9 Correct 53 ms 8224 KB Output is correct
10 Correct 5 ms 2940 KB Output is correct
11 Correct 76 ms 10012 KB Output is correct
12 Correct 87 ms 11812 KB Output is correct
13 Correct 4 ms 2936 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 13688 KB Output is correct
2 Correct 85 ms 13688 KB Output is correct
3 Correct 55 ms 10104 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3704 KB Output is correct
6 Correct 23 ms 5240 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 41 ms 6648 KB Output is correct
9 Correct 53 ms 8224 KB Output is correct
10 Correct 5 ms 2940 KB Output is correct
11 Correct 76 ms 10012 KB Output is correct
12 Correct 87 ms 11812 KB Output is correct
13 Correct 4 ms 2936 KB Output is correct
14 Incorrect 4 ms 2808 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 13688 KB Output is correct
2 Correct 85 ms 13688 KB Output is correct
3 Correct 55 ms 10104 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3704 KB Output is correct
6 Correct 23 ms 5240 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 41 ms 6648 KB Output is correct
9 Correct 53 ms 8224 KB Output is correct
10 Correct 5 ms 2940 KB Output is correct
11 Correct 76 ms 10012 KB Output is correct
12 Correct 87 ms 11812 KB Output is correct
13 Correct 4 ms 2936 KB Output is correct
14 Incorrect 4 ms 2808 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 6044 KB Output is correct
2 Correct 681 ms 6064 KB Output is correct
3 Correct 695 ms 6000 KB Output is correct
4 Correct 710 ms 6136 KB Output is correct
5 Correct 679 ms 6028 KB Output is correct
6 Correct 739 ms 6492 KB Output is correct
7 Correct 726 ms 6136 KB Output is correct
8 Correct 693 ms 6000 KB Output is correct
9 Correct 675 ms 6056 KB Output is correct
10 Correct 691 ms 6144 KB Output is correct
11 Correct 6 ms 2808 KB Output is correct
12 Execution timed out 1049 ms 3608 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 13688 KB Output is correct
2 Correct 85 ms 13688 KB Output is correct
3 Correct 55 ms 10104 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3704 KB Output is correct
6 Correct 23 ms 5240 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 41 ms 6648 KB Output is correct
9 Correct 53 ms 8224 KB Output is correct
10 Correct 5 ms 2940 KB Output is correct
11 Correct 76 ms 10012 KB Output is correct
12 Correct 87 ms 11812 KB Output is correct
13 Correct 4 ms 2936 KB Output is correct
14 Correct 6 ms 2936 KB Output is correct
15 Correct 9 ms 2936 KB Output is correct
16 Incorrect 12 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 80 ms 13688 KB Output is correct
2 Correct 85 ms 13688 KB Output is correct
3 Correct 55 ms 10104 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3704 KB Output is correct
6 Correct 23 ms 5240 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 41 ms 6648 KB Output is correct
9 Correct 53 ms 8224 KB Output is correct
10 Correct 5 ms 2940 KB Output is correct
11 Correct 76 ms 10012 KB Output is correct
12 Correct 87 ms 11812 KB Output is correct
13 Correct 4 ms 2936 KB Output is correct
14 Incorrect 4 ms 2808 KB Output isn't correct
15 Halted 0 ms 0 KB -