Submission #123030

#	Time	Username	Problem	Language	Result	Execution time	Memory
123030		MAMBA	Dreaming (IOI13_dreaming)	C++17	100 / 100	132 ms	18680 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i , j , k) for (int i = j; i < (int)k; i++)

typedef vector<int> vi;

constexpr int MAXN = 1e5 + 10;

inline bool smin(int &l, int r) {
	if (r < l) return l = r , true;
	return false;
}

inline bool smax(int &l, int r) {
	if (l < r) return l = r, true;
	return false;
}


vi adj[MAXN];
int res, pd[MAXN], dpU[MAXN], dpD[MAXN];
int a[MAXN], b[MAXN], t[MAXN];

void dfsD(int v, int par = -1) {
	dpD[v] = 0;
	for (auto e : adj[v]) {
		int u = a[e] ^ b[e] ^ v;
		if (u ^ par) {
			dfsD(u , v);
			smax(dpD[v] , dpD[u] + t[e]);
		}
	}
}

void dfsU(int v, int& root, int par = -1) {
	pd[v] = max(dpD[v] , dpU[v]);
	if (pd[v] < pd[root]) root = v;
	smax(res , pd[v]);

	auto solve = [&]() {
		int worst = dpU[v];
		for (auto e : adj[v]) {
			int u = a[e] ^ b[e] ^ v;
			if (u ^ par) {
				smax(dpU[u] , worst + t[e]);
				smax(worst , dpD[u] + t[e]);
			}
		}
	};

	solve();
	reverse(all(adj[v]));
	solve();

	for (auto e :adj[v]) {
		int u = a[e] ^ b[e] ^ v;
		if (u ^ par)
			dfsU(u , root , v);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

	rep(i , 0 , N) adj[i].clear();

	rep(i , 0 , M) {
		tie(a[i] , b[i] , t[i]) = make_tuple(A[i] ,B[i] ,T[i]);
		adj[A[i]].pb(i);
		adj[B[i]].pb(i);
	}

	memset(pd , 0 , sizeof(pd));
	memset(dpU , 0 , sizeof(dpU));
	memset(dpD , 0 , sizeof(dpD));
	res = 0;

	vi vec;

	rep(i , 0 , N)
		if (!pd[i]) {
			int root = i;
			dfsD(i);
			dfsU(i , root);
			vec.pb(root);
		}
	sort(all(vec) , [](int l , int r) { return pd[l] > pd[r]; });

	int lres = 1e9;
	int g = min(3 , (int)vec.size());
	rep(i , 0 , g) {
		int worst = 0;
		rep(j , 0 , g) 
			if (i ^ j) {
				smax(worst , pd[vec[i]] + pd[vec[j]] + L);
				rep(z , 0 , g)
					if (z ^ i && z ^ j)
						smax(worst , pd[vec[z]] + pd[vec[j]] + 2 * L);
			}
		smin(lres , worst);
	}
	return max(lres , res);
}

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