Submission #163534

#	Time	Username	Problem	Language	Result	Execution time	Memory
163534		kostia244	Dreaming (IOI13_dreaming)	C++17	100 / 100	131 ms	20428 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
const int maxn = 100100;
int n;
vector<pi> g[maxn];
pi dp[maxn];
int vis[maxn];
ll d, ans = 0;;
void dfs(int v) {
	ll x, y;
	x=y=0;
	vis[v] = 1;
	for(auto i: g[v]) {
		if(vis[i.first]) continue;
		dfs(i.first);
		ll t = i.second + dp[i.first].first;
		if(x<t) y = x, x = t;
		else if(y < t) y = t;
	}
	ans = max(ans, x+y);
	dp[v] = {x, y};
}
void findd(int v, int p, ll len = 0) {
	d = min(d, max(len, dp[v].first));
	for(auto i : g[v]) {
		if(i.first==p) continue;
		ll x = len+i.second;
		if(dp[i.first].first+i.second!=dp[v].first) x = max(x, dp[v].first+i.second);
		else x = max(x, dp[v].second+i.second);
		findd(i.first, v, x);
	}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N;
	if(n==1) return 0;
	for(int i = 0; i < M; i++) {
		g[A[i]].pb({B[i], T[i]});
		g[B[i]].pb({A[i], T[i]});
	}
	vector<ll> x;
	for(int i = 0; i < n; i++) {
		if(vis[i]) continue;
		dfs(i);
		d = 1e17;
		findd(i, i);
		x.pb(d);
	}
	sort(x.rbegin(), x.rend());
	ans = max(ans, x[0]);
	if(x.size()>1) ans = max(ans, x[0]+L+x[1]);
	if(x.size()>2) ans = max(ans, x[2]+L+L+x[1]);
    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