Submission #897547

#	Time	Username	Problem	Language	Result	Execution time	Memory
897547		oblantis	Dreaming (IOI13_dreaming)	C++17	100 / 100	54 ms	19416 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const ll inf = 1e18 + 10000;
const int mod = 1e9+7;
const int maxn = 1e5 + 12;
vt<pii> g[maxn];
ll mx[maxn][2], ret, rad;
bool was[maxn];
void dfs(int v){
	was[v] = 1;
	for(auto i : g[v]){
		if(!was[i.ff]){
			dfs(i.ff);
			ll x = mx[i.ff][0] + i.ss;
			if(mx[v][0] < x)mx[v][1] = mx[v][0], mx[v][0] = x;
			else if(mx[v][1] < x)mx[v][1] = x;
		}
	}
}
void rlx(int v, ll x, int pr){
	for(auto i : g[v]){
		if(i.ff != pr){
			if(mx[v][0] == i.ss + mx[i.ff][0])rlx(i.ff, max(x, mx[v][1]) + i.ss, v);
			else rlx(i.ff, max(x, mx[v][0]) + i.ss, v);
		}
	}
	if(x > mx[v][0])mx[v][1] = mx[v][0], mx[v][0] = x;
	else if(x > mx[v][1])mx[v][1] = x;
	ret = max(ret, mx[v][0] + mx[v][1]);
	rad = min(rad, mx[v][0]);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	for(int i = 0; i < m; i++){
		g[a[i]].pb({b[i], t[i]});
		g[b[i]].pb({a[i], t[i]});
	}
	vt<ll> sr;
	for(int i = 0; i < n; i++){
		if(!was[i]){
			dfs(i);
			rad = mx[i][0];
			rlx(i, 0, 0);
			sr.pb(rad);
		}
	}
	sort(all(sr));
	if(sr.size() > 1)ret = max(ret, l + sr.back() + sr[sr.size() - 2]);
	if(sr.size() > 2)ret = max(ret, l + l + sr[sr.size() - 2] + sr[sr.size() - 3]);
	return ret;
}

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