Submission #246975

#	Time	Username	Problem	Language	Result	Execution time	Memory
246975		Nightlight	Dreaming (IOI13_dreaming)	C++14	0 / 100	59 ms	10488 KiB

dreaming

#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;
		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;
		}
		DFS(v, u);
	}
}

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 = max(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 = 0;
			DFS(i, 0);
			reroot(i, 0);
			big[p++] = res;
		}
	}
	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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23