Submission #836006

#	Time	Username	Problem	Language	Result	Execution time	Memory
836006		Halym2007	Dreaming (IOI13_dreaming)	C++17	100 / 100	77 ms	14248 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define ff first
#define pb push_back
#define ss second
#define sz size()

bool vis[N];
int mx, jog1, Diaval;
vector <int> members, roots, w;
int dp[N];
vector <pair <int, int>> v[N];
void dfs (int x, int pr) {
	vis[x] = 1;
	members.pb (x);
	for (auto i : v[x]) {
		if (i.ff == pr) continue;
		dfs (i.ff, x);
	}
}

void solve (int x, int pr, int val) {
	if (val > mx) {
		mx = val;
		jog1 = x;
	}
	dp[x] = max (val, dp[x]);
	for (auto i : v[x]) {
		if (i.ff == pr) continue;
		solve (i.ff, x, val + i.ss);
	}
} 


int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	for (int i = 0; i < m; ++i) {
		v[a[i]].pb ({b[i], t[i]});
		v[b[i]].pb ({a[i], t[i]});
	}
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			dfs (i, -1);
			roots.pb (i);
		}
	}
	for (int root : roots) {
		members.clear();
		dfs (root, -1);
		mx = 0;
		solve (root, -1, 0);
		int dia1 = jog1;
		mx = 0;
		solve (jog1, -1, 0);
		int dia2 = jog1;
		Diaval = max (Diaval, mx);
		solve (dia1, -1, 0);
		solve (dia2, -1, 0);
		int mn = 1e9;
		for (int member : members) {
			mn = min (dp[member], mn);
		}
		w.pb (mn);
	}
	sort (w.begin(), w.end());
	reverse (w.begin(), w.end());
	int jogap = 0;
	if ((int)w.sz >= 2) {
		jogap = max (jogap, w[0] + w[1] + l);
	}	
	if ((int)w.sz >= 3) {
		jogap = max (jogap, w[1] + w[2] + 2*l);
	}
	return max (jogap, Diaval);
}
//
//#define MAX_N 100000
//
//static int A[MAX_N];
//static int B[MAX_N];
//static int T[MAX_N];
//
//int main() {
//	freopen("input.in", "r", stdin);
//	int n, M, L, i;
//	cin >> n >> M >> L;
//	for (i = 0; i < M; i++)
//		cin >> A[i] >> B[i] >> T[i];
//	int answer = travelTime(n, M, L, A, B, T);
//	cout << answer << "\n";
//
//	return 0;

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