Submission #246995

#	Time	Username	Problem	Language	Result	Execution time	Memory
246995		Nightlight	Dreaming (IOI13_dreaming)	C++14	100 / 100	114 ms	18040 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;
		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 != -1) {
		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);
//	cout << u << ":\n";
//	cout << best[u].first << " " << best[u].second << "\n";
//	cout << best2[u].first << " " << best2[u].second << "\n\n";
	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++) {
//		cout << a[i] << " " << b[i] << " " << t[i] << "\n";
		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, -1);
			reroot(i, -1);
			big[p++] = res;
//			cout << i << " " << res << "\n";
		}
	}
//	for(int i = 0; i < p; i++) cout << big[i] << " ";
	sort(big, big + p, greater<int>());
//	for(int i = 0; i < p; i++) cout << big[i] << " ";
	cout << "\n";
	if(p > 1) ans = max(ans, big[0] + big[1] + L);
	if(p > 2) ans = max(ans, big[1] + big[2] + L * 2);
	return ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23