Submission #1180952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180952		trvhung	Dreaming (IOI13_dreaming)	C++20	100 / 100	53 ms	17352 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int maxn = 1e5 + 5;
int n, m, l, diameter, diaL, diaR, sum[maxn], up[maxn], p[maxn], lps[maxn], curCc, cc[maxn], sub[maxn], pref[maxn], suf[maxn];
vector<pair<int, int>> adj[maxn];
vector<int> vec;
bool vis[maxn], onLine[maxn];

void find_diameter(int u, int par, int d, int &mx, int &nd) {
	vis[u] = true; cc[u] = curCc;
	if (maximize(mx, d)) nd = u;
	
	for (auto g: adj[u]) {
		int v = g.F, w = g.S;
		if (v != par) {
			p[v] = u; up[v] = w;
			find_diameter(v, u, d + w, mx, nd);
		}
	}
}

void dfs(int u, int par, int mx) {
	lps[u] = mx;
	for (auto g: adj[u]) {
		int v = g.F, w = g.S;
		if (v == par || onLine[v]) continue;
		dfs(v, u, mx + w);
	}
} 

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N; m = M; l = L;
	for (int i = 0; i < M; ++i) {
		adj[A[i] + 1].push_back(make_pair(B[i] + 1, T[i]));
		adj[B[i] + 1].push_back(make_pair(A[i] + 1, T[i]));
	}

	for (int i = 1; i <= n; ++i)
		if (!vis[i]) {
			curCc++;

			diameter = -1; find_diameter(i, 0, 0, diameter, diaL);
			diameter = -1; find_diameter(diaL, 0, 0, diameter, diaR);

			int u = diaR; vec.clear();
			while (u != diaL) onLine[u] = true, vec.push_back(u), u = p[u];
			vec.push_back(diaL); onLine[diaL] = true;

			int sz = (int) vec.size();

			sum[1] = 0;
			for (int j = 2; j <= sz; ++j)
				sum[j] = sum[j - 1] + up[vec[j - 2]];

			for (int j = 0; j < sz; ++j) {
				int mx = max(sum[j + 1], sum[sz] - sum[j + 1]);
				dfs(vec[j], 0, mx);
			}
		}	

	if (curCc == 1) return *max_element(lps + 1, lps + 1 + n);

	for (int i = 1; i <= curCc; ++i) sub[i] = INF;
	for (int i = 1; i <= n; ++i) 
		minimize(sub[cc[i]], lps[i]);

	pref[0] = suf[curCc + 1] = 0;

	pref[1] = sub[1];
	for (int i = 2; i <= curCc; ++i)
		pref[i] = max(pref[i - 1], sub[i]);

	suf[curCc] = sub[curCc];
	for (int i = curCc - 1; i >= 1; --i)
		suf[i] = max(suf[i + 1], sub[i]);

	multiset<int> s;
	for (int i = 1; i <= curCc; ++i)
		s.insert(sub[i]);

	int res = INF, mxAll = *max_element(lps + 1, lps + 1 + n);
	for (int i = 1; i <= curCc; ++i) {
		int mx = mxAll;
		maximize(mx, sub[i] + l + max(pref[i - 1], suf[i + 1]));
		if (curCc > 2) {
			s.erase(s.find(sub[i]));
			auto it = s.rbegin();
			auto it1 = s.end(); it1--; it1--;
			maximize(mx, *it + *it1 + 2 * l);
			s.insert(sub[i]);
		}
		minimize(res, mx);
	}

	return 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