Submission #737704

#	Time	Username	Problem	Language	Result	Execution time	Memory
737704		TheOpChicken	Dreaming (IOI13_dreaming)	C++17	100 / 100	118 ms	21316 KiB

dreaming

#include <iostream>
#include <vector>
#include <set>
#include "dreaming.h"
using namespace std;

const int maxN = 1e5 + 5;

long long dist[2][maxN], visited[maxN];

vector<pair<long long, long long> > adj[maxN];

vector<int> component;

multiset<pair<long long, long long > > comps;

pair<long long, int> dfs(int node, int parent, long long cur_dist, long long *store, bool need_add){
	visited[node] = 1;
	if (need_add) component.push_back(node);
	else store[node] = cur_dist;

	pair<long long, int> ans = make_pair(cur_dist, node);
	for (pair<int, int> child: adj[node]){
		if (child.first == parent) continue;
		ans = max(ans, dfs(child.first, node, cur_dist+child.second, store, need_add));
	}

	return ans;
}

int travelTime(int n, int m, int L, int a[], int b[], int t[]){
	for (int i = 0; i < m; i++){
		adj[a[i]].push_back(make_pair(b[i], t[i]));
		adj[b[i]].push_back(make_pair(a[i], t[i]));
	}

	for (int i = 0; i < n; i++){
		if (visited[i]) continue;
		component.clear();

		pair<long long, int> furthest = dfs(i, -1, 0, dist[0], true);
		pair<long long, int> next_furthest = dfs(furthest.second, -1, 0, dist[0], false);
		dfs(next_furthest.second, -1, 0, dist[1], false);

		long long mini_max = 1e18;
		for (int node: component) mini_max = min(mini_max, max(dist[0][node], dist[1][node]));
		
		comps.insert(make_pair(mini_max, next_furthest.first));
	}

	while(comps.size() > 1){
		pair<long long, long long> first = *comps.begin();
		pair<long long, long long> second = *comps.rbegin(); 

		comps.erase(comps.begin());
		comps.erase(--comps.end());

		pair<long long, long long> new_comp;
		new_comp.first = min(max(first.first, second.first + L), max(second.first, first.first + L));
		new_comp.second = max(first.second, max(second.second, first.first + second.first + L));
		comps.insert(new_comp);
	}

	pair<long long, long long> ans = *comps.begin();
	return ans.second;

}

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