| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 741601 |
2023-05-14T12:58:04 Z |
MODDI |
Dreaming (IOI13_dreaming) |
C++14 |
|
37 ms |
14268 KB |
#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
using namespace std;
vector<pair<int,long long> > G[100100];
bool vis[100100];
ll ans, help = 0;
void dfs(int at, long long dist, vector<pair<int, long long> >& paths){
vis[at] = true;
paths.push_back(make_pair(at, dist));
for(auto next : G[at]){
if(!vis[next.first]){
dfs(next.first, dist + next.second, paths);
}
}
}
void solve(int start){
vector<pair<int, long long> > distance1, distance2;
dfs(start, 0, distance1);
int fur_node1 = -1;
long long fur_len1 = -1;
for(int i = 0; i < distance1.size(); i++){
if(fur_len1 < distance1[i].second){
fur_len1 = distance1[i].second;
fur_node1 = distance1[i].first;
}
}
distance1.clear();
dfs(fur_node1, 0, distance1);
int fur_node2 = -1;
long long fur_len2 = -1;
map<int, long long> store;
for(int i = 0; i < distance1.size(); i++){
store[distance1[i].first] = distance1[i].second;
if(fur_len2 < distance1[i].second){
fur_len2 = distance1[i].second;
fur_node2 = distance1[i].first;
}
}
help = max(help, fur_len2);
dfs(fur_node2, 0, distance2);
for(int i = 0; i < distance2.size(); i++){
ans = min(ans, max(distance2[i].second, store[distance2[i].first]));
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(vis, false, sizeof vis);
for(int i = 0; i < M; i++){
G[A[i]].pb(mp(B[i], T[i]));
G[B[i]].pb(mp(A[i], T[i]));
}
vector<ll> arr;
for(int i = 0; i < N; i++){
if(!vis[i]){
ans = 2e9;
solve(i);
arr.pb(ans);
}
else
continue;
}
sort(arr.rbegin(), arr.rend());
if(arr.size() == 1) return max(arr[0], help);
else
return max(max(help, arr[0] + arr[1] + L), arr[1] + arr[2] + 2 * L);
}
Compilation message
dreaming.cpp: In function 'void solve(int)':
dreaming.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i = 0; i < distance1.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0; i < distance1.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0; i < distance2.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
14268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
14268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
5720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
14268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
