Submission #897757

#	Time	Username	Problem	Language	Result	Execution time	Memory
897757		aqxa	Dreaming (IOI13_dreaming)	C++17	10 / 100	1058 ms	26960 KiB

dreaming

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

using ll = long long; 

const int N = 1e5; 

#define fs first
#define sc second
#define mp make_pair

vector<pair<int, int>> g[N]; 
int vis[N], mxd[N], mx[N]; 
multiset<int> ms[N]; 

void dfs(int x, int p) {
	vis[x] = 1; 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			dfs(u, x); 
			mxd[x] = max(mxd[x], mxd[u] + w);
		}
	}
}
void dfs2(int x, int p, int f) {
	ms[x].insert(f); 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			ms[x].insert(mxd[u] + w); 
		}
	}
	mx[x] = *(ms[x].rbegin()); 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			ms[x].erase(ms[x].lower_bound(mxd[u] + w)); 
			dfs2(u, x, *(ms[x].rbegin()) + w); 
			ms[x].insert(mxd[u] + w); 
		}
	}
}
int dfs3(int x, int p) {
	int res = mx[x]; 
	for (auto [u, w]: g[x]) {
		if (u == p) continue; 
		res = min(res, dfs3(u, x)); 
	}
	return res; 
}

int dbg[N]{ 0 }; 
int slow(int x, int p) {
	int mx = 0; 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			mx = max(mx, slow(u, x) + w); 
		}
	}
	return mx; 
}

int travelTime(int n, int m, int l, int u[], int v[], int t[]){
	for (int i = 0; i < n; ++i) {
		vis[i] = 0; 
		mxd[i] = 0; 
		mx[i] = 0; 
	}
	for (int i = 0; i < m; ++i) {
		g[u[i]].push_back(mp(v[i], t[i])); 
		g[v[i]].push_back(mp(u[i], t[i])); 
	}

	vector<int> mxdist; 
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			dfs(i, -1); 
			dfs2(i, -1, 0); 
			mxdist.push_back(dfs3(i, -1)); 
		}
	}
	for (int i = 0; i < n; ++i) {
		assert(slow(i, -1) == mx[i]); 
	}
	sort(mxdist.begin(), mxdist.end()); 
	
	int ans = 0; 
	for (int i = 0; i < n; ++i) {
		ans = max(ans, mx[i]); 
	}

	int sz = (int) mxdist.size(); 
	assert(sz > 0); 
	if (sz == 1) {
		assert(m + 1 == n); 
	} else {
		ans = max(ans, mxdist[sz - 1] + mxdist[sz - 2] + l); 
	}

	// for (int i = 0; i < n; ++i) {
	// 	cout << "! " << i << ' ' << mx[i] << '\n';
	// }

  	return ans; 
}


// int32_t main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	int nn = 4, M = 2, L = 2; 
// 	int A[]{1, 0};//{0,8,2,5,5,1,1,10};
// 	int B[]{2, 4};//{8,2,7,11,1,3,9,6}; 
// 	int C[]{1000, 2000};//{4,2,4,3,7,1,5,3};
	
// 	cout << "answer: " << travelTime(nn, M, L, A, B, C); 

// 	return 0; 
// }	

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