Submission #433210

#	Time	Username	Problem	Language	Result	Execution time	Memory
433210		hibye1217	Dreaming (IOI13_dreaming)	C++17	100 / 100	119 ms	20484 KiB

dreaming

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

typedef long long ll;
typedef pair<ll, ll> pl2;
#define fr first
#define sc second

#define all(v) v.begin(),v.end()

vector<pl2> adj[100020];
int par[100020];

inline int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}

inline void uni(int a, int b){
	int pa = fnd(a), pb = fnd(b);
	par[pa] = pb;
}

vector<int> upd;
pl2 res = {-1, -1};
void dfs1(int now, int pre, ll dis){
	upd.push_back(now);
	if (res.sc < dis){ res = {now, dis}; }
	for (pl2 p : adj[now]){
		int nxt = p.fr; ll dst = p.sc;
		if (nxt == pre){ continue; }
		dfs1(nxt, now, dis+dst);
	}
}

pl2 chk[100020];
void dfs2(int now, int pre, ll dis){
	chk[now] = {pre, dis};
	if (res.sc < dis){ res = {now, dis}; }
	for (pl2 p : adj[now]){
		int nxt = p.fr; ll dst = p.sc;
		if (nxt == pre){ continue; }
		dfs2(nxt, now, dis+dst);
	}
}

bool pac[100020];
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i = 0; i < N; i++){ par[i] = i; }
	for (int i = 0; i < M; i++){
		adj[ A[i] ].push_back({ B[i], T[i] });
		adj[ B[i] ].push_back({ A[i], T[i] });
		uni(A[i], B[i]);
	}
	vector<ll> ansv;
	ll ret = 0;
	for (int i = 0; i < N; i++){
		int pai = fnd(i);
		if (pac[pai]){ continue; } pac[pai] = 1;
		res = {-1, -1}; dfs1(i, -1, 0); int mxp = res.fr;
		res = {-1, -1}; dfs2(mxp, -1, 0); int p = res.fr;
		vector<int> v;
		while (p != -1){ v.push_back(p); p = chk[p].fr; }
		int vl = v.size(); vector<ll> prf(vl);
		for (int i = 0; i < vl; i++){
			prf[i] = chk[ v[i] ].sc;
			ret = max(ret, prf[i]);
		}
		ll ans = 1e15;
		for (int i = 0; i < vl; i++){
			ll res = max( abs(prf[0]-prf[i]), abs(prf[i]-prf[vl-1]) );
			ans = min(ans, res);
		}
		//cout << "ANSV " << i << ' ' << ans << endl;
		ansv.push_back(ans);
	}
	sort(all(ansv), [](ll a, ll b){ return a > b; });
	if (ansv.size() == 1){ ret = max(ret, ansv[0]); }
	else if (ansv.size() == 2){ ret = max(ret, ansv[0]+L+ansv[1]); }
	else{ ret = max({ ret, ansv[0]+L+ansv[1], ansv[1]+L+L+ansv[2] }); }
	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