Submission #967194

#	Time	Username	Problem	Language	Result	Execution time	Memory
967194		SmuggingSpun	Dreaming (IOI13_dreaming)	C++17	100 / 100	77 ms	18392 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool maximize(T& a, T b){
	if(a < b){
		a = b;
		return true;
	}
	return false;
}
template<class T>bool minimize(T& a, T b){
	if(a > b){
		a = b;
		return true;
	}
	return false;
}
const int lim = 1e5 + 5;
vector<pair<int, int>>e[lim];
bitset<lim>vis;
int ans = 0, dist[3][lim], max_d, A, B;
vector<pair<int, int>>vertex;
void dfs(const int id, int s, bool upd, int& upd_vertex, int p = -1){
	maximize(ans, dist[id][s]);
	for(auto& [d, w] : e[s]){
		if(d != p){
			dist[id][d] = dist[id][s] + w;
			dfs(id, d, upd, upd_vertex, s);
		}
	}
	if(upd && maximize(max_d, dist[id][s])){
		upd_vertex = s;
	}
}
pair<int, int>find_root(int root){
	queue<int>q;
	q.push(root);
	vis.set(root);
	int min_d = INT_MAX, ans;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(minimize(min_d, max(dist[1][u], dist[2][u]))){
			ans = u;
		}
		for(auto& [v, w] : e[u]){
			if(!vis.test(v)){
				q.push(v);
				vis.set(v);
			}
		}
	}
	return make_pair(min_d, ans);
}
void solve(int root){
	max_d = -1;
	dfs(0, root, true, A);
	max_d = -1;
	dfs(1, A, true, B);
	dfs(2, B, false, A);
	vertex.emplace_back(find_root(root));
}
int travelTime(int n, int m, int L, int a[], int b[], int t[]){
	for(int i = 0; i < m; i++){
		e[a[i]].emplace_back(b[i], t[i]);
		e[b[i]].emplace_back(a[i], t[i]);
	}
	vis.reset();
	for(int i = 0; i < n; i++){
		if(!vis.test(i)){
			solve(i);
		}
	}
	sort(vertex.begin(), vertex.end());
	if(vertex.size() > 1){
		maximize(ans, vertex.back().first + vertex[int(vertex.size()) - 2].first + L);
	}
	if(vertex.size() > 2){
		maximize(ans, vertex[int(vertex.size()) - 2].first + vertex[int(vertex.size()) - 3].first + (L << 1));
	}
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'std::pair<int, int> find_root(int)':
dreaming.cpp:39:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |  int min_d = INT_MAX, 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