Submission #170336

#	Time	Username	Problem	Language	Result	Execution time	Memory
170336		ngmh	Dreaming (IOI13_dreaming)	C++11	100 / 100	127 ms	17656 KiB

dreaming

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

typedef pair<int, int> pi;

int d[100000], fr[100000], v[100000];
vector<int> radii;
vector<pi> adj[100000];

pi dfs1(long long node, long long parent, long long distance){
	v[node] = 1;
	pi p = pi(node, distance);
	for(auto it : adj[node]){
		if(!d[it.first] && it.first != parent){
			pi q = dfs1(it.first, node, distance+it.second);
			if(q.second > p.second) p = q;
		}
	}
	return p;
}

pi dfs2(long long node, long long parent, long long distance){
	v[node] = 1;
	d[node] = distance;
	fr[node] = parent;
	pi p = pi(node, distance);
	for(auto it : adj[node]){
		if(!d[it.first] && it.first != parent){
			pi q = dfs2(it.first, node, distance+it.second);
			if(q.second > p.second) p = q;
		}
	}
	return p;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	int c, maxd = 0, r, ans = 0;
	pi f, l;
	for(int i = 0; i < M; i++){
		adj[A[i]].push_back(pi(B[i], T[i]));
		adj[B[i]].push_back(pi(A[i], T[i]));
	}
	memset(fr, -1, sizeof(fr));
	for(int i = 0; i < N; i++){
		if(v[i]) continue;
		f = dfs1(i, i, 0);
		l = dfs2(f.first, f.first, 0);
		maxd = max(maxd, l.second);
		c = l.first;
		r = l.second;
		while(true){
			r = min(r, max(d[c], l.second-d[c]));
			if(c == fr[c]) break;
			c = fr[c];
		}
		radii.push_back(r);
	}
	sort(radii.begin(), radii.end());
	reverse(radii.begin(), radii.end());
	ans = maxd;
	if(radii.size() > 1) ans = max(ans, radii[0]+radii[1]+L);
	if(radii.size() > 2) ans = max(ans, radii[1]+radii[2]+2*L);
	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