Submission #1245404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245404		Nurislam	Dreaming (IOI13_dreaming)	C++20	100 / 100	76 ms	33868 KiB

dreaming

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


const int inf = 2e9;

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	vector<vector<array<int,2>>> g(n);
	
	for(int i = 0; i < m; i ++ ) {
		g[a[i]].push_back({b[i], t[i]});
		g[b[i]].push_back({a[i], t[i]});
	};
	
	
	
	vector<int> ds, us(n), sub(n,0);
	
	function<void(int,int)> st = [&](int ps, int pr) {
		us[ps] = 1;
		for(auto [to, w] : g[ps]) {
			if(to == pr)continue;
			st(to, ps);
			sub[ps] = max(sub[ps], sub[to] + w);
		};
	};
	
	int mn = inf;
	function<void(int, int, int)> dfs = [&](int ps, int dad, int dw){
		
		vector<int> pr(g[ps].size()+1), sf(g[ps].size()+1);
		for(int i = 1; i <= (int)g[ps].size(); i ++ ) {
			auto &[to, w] = g[ps][i-1];
			pr[i] = pr[i-1];
			if(to == dad)continue;
			pr[i] = max(pr[i], sub[to]+w);
		};
		for(int i = g[ps].size()-1; i >= 0; i -- ) {
			auto &[to, w] = g[ps][i];
			sf[i] = sf[i+1];
			if(to == dad)continue;
			sf[i] = max(sf[i], sub[to]+w);
		};
		for(int i = 0; i < (int)g[ps].size(); i ++ ) {
			auto &[to, w] = g[ps][i];
			if(to == dad)continue;
			dfs(to, ps, max({w + dw, sf[i+1]+w, pr[i]+w}));
		};
		
		
		mn = min(mn, max(sub[ps], dw));
		//cout << ps << ' ' << dad << ' ' << dw << ' ' << pr.back() << '\n';
	};
	
	for(int i = 0; i < n; i ++ ) {
		if(us[i])continue;
		st(i, i);
		mn = inf;
		dfs(i, i, 0);
		ds.push_back(mn);
	};
	
	int ans = 0;
		
	sort(ds.rbegin(), ds.rend());
	if(ds.size() > 1) {
		ans = max(ds[0]+ds[1]+l, ans);
	};
	if(ds.size() > 2) {
		ans = max(ds[1] + ds[2] + l + l, ans);
	};
	//for(int i : ds) cout << i << ' ';
	//cout << '\n';
	
	vector<int> ls, ch(n);
	function<void(int,int, vector<int>&)> dfs2 = [&](int ps, int pr, vector<int> &d) {
		ls.push_back(ps);
		ch[ps] = 1;
		for(auto [to, w] : g[ps]) {
			if(to == pr)continue;
			d[to] = d[ps] + w;
			dfs2(to, ps, d);
		};
	};
	
	vector<int> d(n, 0);
	for(int i = 0; i < n; i ++ ) {
		if(ch[i])continue;
		dfs2(i,i,d);
		
		int nt = ls[0];
		for(int x : ls)
			if(d[nt] < d[x])nt = x;
		d[nt] = 0;
		dfs2(nt,nt,d);
		for(int x : ls) ans = max(ans, d[x]);
		ls.clear();
	}
	
	
	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