Submission #90792

#	Time	Username	Problem	Language	Result	Execution time	Memory
90792		arman_ferdous	Dreaming (IOI13_dreaming)	C++17	100 / 100	145 ms	12036 KiB

dreaming

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

const int N = 1e5+10;
int n, dist[N];
vector< pair<int,int> > g[N], center;

int mx, sc;
void dfs0(int u, int f, int d) {
	dist[u] = d;
	if(dist[u] > mx) mx = dist[u], sc = u;
	for(auto e : g[u]) if(e.first != f)
		dfs0(e.first, u, d + e.second);
}

void dfs1(int u, int f, int d) {
	dist[u] = d;
	if(dist[u] > mx) mx = dist[u], sc = u;
	for(auto e : g[u]) if(e.first != f)
		dfs1(e.first, u, d + e.second);
}
void dfs2(int u, int f, int d) {
	dist[u] = max(dist[u], d);
	if(dist[u] < mx) mx = dist[u], sc = u;
	for(auto e : g[u]) if(e.first != f)
		dfs2(e.first, u, d + e.second);
}

int travelTime(int N_, int M, int L, int A[], int B[], int T[]) {
	n = N_;
	for(int i = 0; i < M; i++) {
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
	}
	memset(dist,-1,sizeof dist);
	for(int i = 0; i < n; i++) {
		if(dist[i] == -1) {
			mx = -1; dfs0(i,-1,0);
			mx = -1; dfs1(sc,-1,0);
			mx = (int)2e9; dfs2(sc,-1,0);
			center.push_back({-dist[sc], sc});
		}
	} sort(center.begin(), center.end());
	int sz = center.size();
	for(int i = 1; i < sz; i++) {
		g[center[0].second].push_back({center[i].second, L});
		g[center[i].second].push_back({center[0].second, L});
	}
	memset(dist,-1,sizeof dist);
	mx = -1; dfs0(0,-1,0);
	mx = -1; dfs1(sc,-1,0);
	dfs2(sc,-1,0);

	int ans = 0;
	for(int i = 0; i < n; i++)
		ans = max(ans, dist[i]);
	return ans;
}

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