oj.uz

Submission #246983

# Submission time Handle Problem Language Result Execution time Memory
246983 2020-07-10T17:06:28 Z Nightlight Dreaming (IOI13_dreaming) C++14
0 / 100
 67 ms 12968 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int N, M, L;
int big[100005];
bool vis[100005];
vector<pii> adj[100005];
pii best[100005];
pii best2[100005];
int p;
int ans;
int res;

void DFS(int u, int p) {
	int v, w;
	vis[u] = 1;
	for(pii now : adj[u]) {
		v = now.first, w = now.second;
		if(v == p) continue;
		DFS(v, u);
		if(best[v].first + w > best[u].first) {
			best2[u] = best[u];
			best[u].first = best[v].first + w;
			best[u].second = v;
		}else if(best[v].first + w > best2[u].first) {
			best2[u].first = best[v].first + w;
			best2[u].second = v;
		}
	}
}

void reroot(int u, int p, int pw = 0) {
	if(p) {
		if(best[p].second != u) {
			if(best[p].first + pw > best[u].first) {
				best2[u] = best[u];
				best[u].first = best[p].first + pw;
				best[u].second = -1;
			}else if(best[p].first + pw > best2[u].first) {
				best2[u].first = best[p].first + pw;
				best2[u].second = -1;
			}
		}else {
			if(best2[p].first + pw > best[u].first) {
				best2[u] = best[u];
				best[u].first = best2[p].first + pw;
				best[u].second = -1;
			}else if(best2[p].first + pw > best2[u].first) {
				best2[u].first = best2[p].first + pw;
				best2[u].second = -1;
			}
		}
	}
	ans = max(ans, best[u].first + best2[u].first);
	res = min(res, best[u].first);
	for(pii now : adj[u]) {
		if(now.first == p) continue;
		reroot(now.first, u, now.second);
	}
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	N = n, M = m, L = l;
	for(int i = 0; i < N; i++) best[i] = {0, i}, best2[i] = {-1, -1};
	for(int i = 0; i < M; i++) {
		adj[a[i]].emplace_back(b[i], t[i]);
		adj[b[i]].emplace_back(a[i], t[i]);
	}
	for(int i = 0; i < N; i++) {
		if(vis[i] == 0) {
			res = 0x3f3f3f3f;
			DFS(i, 0);
			reroot(i, 0);
			big[p++] = res;
//			cout << i << " " << res << "\n";
		}
	}
	sort(big, big + p);
	if(p > 1) ans = max(ans, big[p] + big[p - 1] + L);
	if(p > 2) ans = max(ans, big[p - 1] + big[p - 2] + L * 2);
	return ans;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12152 KB Output is correct
2 Correct 58 ms 12968 KB Output is correct
3 Correct 43 ms 11256 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 11 ms 3584 KB Output is correct
6 Correct 21 ms 5120 KB Output is correct
7 Incorrect 6 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12152 KB Output is correct
2 Correct 58 ms 12968 KB Output is correct
3 Correct 43 ms 11256 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 11 ms 3584 KB Output is correct
6 Correct 21 ms 5120 KB Output is correct
7 Incorrect 6 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12152 KB Output is correct
2 Correct 58 ms 12968 KB Output is correct
3 Correct 43 ms 11256 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 11 ms 3584 KB Output is correct
6 Correct 21 ms 5120 KB Output is correct
7 Incorrect 6 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12152 KB Output is correct
2 Correct 58 ms 12968 KB Output is correct
3 Correct 43 ms 11256 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 11 ms 3584 KB Output is correct
6 Correct 21 ms 5120 KB Output is correct
7 Incorrect 6 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 12152 KB Output is correct
2 Correct 58 ms 12968 KB Output is correct
3 Correct 43 ms 11256 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 11 ms 3584 KB Output is correct
6 Correct 21 ms 5120 KB Output is correct
7 Incorrect 6 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -