Submission #124431

#	Time	Username	Problem	Language	Result	Execution time	Memory
124431		khulegub	Dreaming (IOI13_dreaming)	C++14	100 / 100	182 ms	17272 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define mp make_pair
#define xx first
#define yy second
#define pb push_back

using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
//don't forget to change the array sizes

vector<vector<pair<int, int> > > to;
int n;
int m;
int l;
bool vis[100010];
int dia, h;
int h1[100010], h2[100010];

void mark(int u){
	vis[u] = 1;
	for (pii vw : to[u]){
		int v = vw.xx;
		if (!vis[v]){
			mark(v);
		}
	}
}
void dosz(int u, int pre){
	int mx1 = 0, mx2 = 0;
	for (pii vw : to[u]){
		int v = vw.xx;
		if (v != pre){
			dosz(v, u);
			if (mx1 < h1[v] + vw.yy){
				mx2 = mx1;
				mx1 = h1[v] + vw.yy;
			}
			else if (mx2 < h1[v] + vw.yy) mx2 = h1[v] + vw.yy;
		}
	}
	h1[u] = mx1;
	h2[u] = mx2;
}
void crawl(int u, int pre){
	h = min(h, max(h1[u], h2[u]));
	dia = max(dia, h1[u]);
	for (pii vw : to[u]){
		int v = vw.xx;
		if (v != pre){
			int tmpu1 = h1[u], tmpv1 = h1[v];
			int tmpu2 = h2[u], tmpv2 = h2[v];
			if (h1[u] == vw.yy + h1[v]){ //take the second
				h1[u] = h2[u];
			}
			if (h1[u] + vw.yy > h1[v]){
				h2[v] = h1[v];
				h1[v] = h1[u] + vw.yy;
			}
			else if (h1[u] + vw.yy > h2[v]) h2[v] = h1[u] + vw.yy;
			crawl(v, u);
			h1[v] = tmpv1, h2[v] = tmpv2;
			h1[u] = tmpu1, h2[u] = tmpu2;
		}
	}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N, m = M, l = L;
	to.resize(n);
	for (int i = 0; i < m; i++){
		to[A[i]].pb(mp(B[i], T[i]) );
		to[B[i]].pb(mp(A[i], T[i]) );
	}
	vector<int> hs;
	int ans = 0;
	for (int i = 0; i < n; i++){
		if (!vis[i]){
			h = 1e9;
			dia = 0;
			dosz(i, i);
			crawl(i, i);
			ans = max(dia, ans); //ans could be diametr of one subtree
			hs.pb(h);
			mark(i);
		}
	}
	sort(hs.rbegin(), hs.rend());
	if (hs.size() > 1){ // 2 or more trees
		ans = max(ans, hs[0] + hs[1] + l);
	}
	if (hs.size() > 2){ // three or more trees
		ans = max(ans, hs[1] + hs[2] + 2*l);
	}
	// cout << ans;
	return ans;
}
// int dfs2(int )

// int main(){
// 	freopen("in.txt", "r", stdin);
// 	cin >> n >> m >> l;
// 	to.resize(n);
// 	for (int i = 0, a, b, t; i < m; i++){
// 		cin >> a >> b >> t;
// 		to[a].pb(mp(b, t));
// 		to[b].pb(mp(a, t));
// 	}

// }
//don't forget to change the array sizes

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