oj.uz

Submission #530541

# Submission time Handle Problem Language Result Execution time Memory
530541 2022-02-25T18:55:22 Z buidangnguyen05 Dreaming (IOI13_dreaming) C++14
0 / 100
 49 ms 12108 KB 
/* input

*/

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
vector<pair<int, int>> adj[N];
vector<int> nodes;
int it, up[N], down[N][2], radius[N], res; bool dd[N];

void calc_down(int x, int par) {
	nodes.push_back(x); dd[x] = 1;
	for (pair<int, int> v : adj[x]) if (v.first != par) {
			int i, w; tie(i, w) = v;
			calc_down(i, x);
			if (down[i][0] + w > down[x][0]) {
				down[x][1] = down[x][0];
				down[x][0] = down[i][0] + w;
			}
			else if (down[i][0] + w > down[x][1]) down[x][1] = down[i][0] + w;
		}
}

void calc_up(int x, int par) {
	for (pair<int, int> v : adj[x]) if (v.first != par) {
			int i, w; tie(i, w) = v;
			up[i] = up[x] + w;
			if (down[i][0] + w == down[x][0]) up[i] = max(up[i], down[x][1] + w);
			else up[i] = max(up[i], down[x][0] + w);
			calc_up(i, x);
		}

	radius[it] = min(radius[it], max(up[x], down[x][0]));
	res = max(res, up[x] + down[x][0]);
}

int travelTime(int n, int m, int l, int x[], int y[], int w[]) {
	for (int i = 0; i < m; ++i) {
		++x[i]; ++y[i];
		adj[x[i]].push_back(make_pair(y[i], w[i]));
		adj[y[i]].push_back(make_pair(x[i], w[i]));
	}

	for (int i = 1; i <= n; ++i) if (!dd[i]) {
			++it; nodes.clear();
			calc_down(i, 0);
			calc_up(i, 0);
			radius[it] = 2e9;
		}

	sort(radius + 1, radius + it + 1, greater<int>());
	if (it > 1) res = max(res, radius[1] + radius[2] + l);
	if (it > 2) res = max(res, radius[2] + radius[3] + 2 * l);

	return res;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12108 KB Output is correct
2 Correct 42 ms 11840 KB Output is correct
3 Correct 26 ms 10368 KB Output is correct
4 Correct 6 ms 4044 KB Output is correct
5 Correct 5 ms 3404 KB Output is correct
6 Correct 10 ms 4812 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Incorrect 1 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12108 KB Output is correct
2 Correct 42 ms 11840 KB Output is correct
3 Correct 26 ms 10368 KB Output is correct
4 Correct 6 ms 4044 KB Output is correct
5 Correct 5 ms 3404 KB Output is correct
6 Correct 10 ms 4812 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Incorrect 1 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12108 KB Output is correct
2 Correct 42 ms 11840 KB Output is correct
3 Correct 26 ms 10368 KB Output is correct
4 Correct 6 ms 4044 KB Output is correct
5 Correct 5 ms 3404 KB Output is correct
6 Correct 10 ms 4812 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -