oj.uz

Submission #967189

# Submission time Handle Problem Language Result Execution time Memory
967189 2024-04-21T13:23:20 Z SmuggingSpun Dreaming (IOI13_dreaming) C++17
0 / 100
 27 ms 13748 KB 
#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, max_d, A, B;
vector<pair<int, int>>vertex;
vector<int>dist[3];
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][root], dist[2][root]))){
			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());
	for(int i = 1; i < vertex.size(); i++){
		maximize(ans, vertex[i].first + vertex[0].first + L);
	}
	return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 1; i < vertex.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> find_root(int)':
dreaming.cpp:40:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |  int min_d = INT_MAX, ans;
      |                       ^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 13748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 7256 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 13748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 11564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 7256 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 13748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -