#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "dreaming.h"
#endif
const int N = 100005;
int dp[N][4];
vector<pair<int, int> > v[N];
vector<int> ve;
bool bo[N];
pair<int, int> ovod(int dg, int op, int mn) {
bo[dg] = 1;
pair<int, int> dr = {0, dg};
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
pair<int, int> p = ovod(v[dg][i].first, dg, mn + v[dg][i].second);
if(p.first > dr.first) dr = p;
}
}
return dr;
}
void ovog(int dg, int op, int mn, int sv) {
ve.push_back(mn);
if(dg == sv) {
ve[0] = -1;
return;
}
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
ovog(v[dg][i].first, dg, mn + v[dg][i].second, sv);
if(ve[0] == -1) return;
}
}
ve.pop_back();
}
void ovoq(int dg, int op) {
dp[dg][0] = dg;
dp[dg][1] = dp[dg][2] = dp[dg][3] = 0;
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
ovoq(v[dg][i].first, dg);
int x = dp[v[dg][i].first][1];
if(x > dp[dg][1]) {
dp[dg][2] = dp[dg][1];
dp[dg][1] = x;
dp[dg][0] = dp[v[dg][i].first][0];
} else if(x > dp[dg][2]) {
dp[dg][2] = x;
}
}
}
}
int ovox(int dg, int op) {
int dr = 0;
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
int x = (v[dg][i].first == dp[dg][0] ? dp[dg][2] : dp[dg][1]);
dp[v[dg][i].first][3] = max(dp[dg][3], x) + v[dg][i].second;
dr = max(dr, ovox(v[dg][i].first, dg));
}
}
return min(dr, max(dp[dg][1], dp[dg][3]));
}
int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
for(int i = 0; i < n; ++i) {
v[i].clear();
bo[i] = 0;
}
for(int i = 0; i < m; ++i) {
v[a[i]].push_back({b[i], c[i]});
v[b[i]].push_back({a[i], c[i]});
}
int dm = 0;
vector<int> wv;
for(int i = 0; i < n; ++i) {
if(!bo[i]) {
int x = 0;
pair<int, int> p = ovod(x = ovod(0, -1, 0).second, -1, 0);
ve.clear();
ovog(x, -1, 0, p.second);
ve[0] = 0;
int a = p.first;
dm = max(dm, a);
for(int i = 1; i < ve.size(); ++i) {
a = min(a, max(ve[i], p.first - ve[i]));
}
ovoq(0, -1);
int b = ovox(0, -1);
wv.push_back((assert(a == b), a = b));
}
}
sort(wv.begin(), wv.end());
reverse(wv.begin(), wv.end());
int dr = 0;
if(wv.size() == 1);
else if(wv.size() == 2) {
dr = wv[0] + wv[1] + l;
} else {
dr = max(wv[0] + wv[1] + l, wv[1] + wv[2] + l + l);
}
return max(dm, dr);
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
return 0;
}
#endif
Compilation message
dreaming.cpp: In function 'std::pair<int, int> ovod(int, int, int)':
dreaming.cpp:16: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]
16 | for(int i = 0; i < v[dg].size(); ++i) {
| ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void ovog(int, int, int, int)':
dreaming.cpp:31: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]
31 | for(int i = 0; i < v[dg].size(); ++i) {
| ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void ovoq(int, int)':
dreaming.cpp:43: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]
43 | for(int i = 0; i < v[dg].size(); ++i) {
| ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int ovox(int, int)':
dreaming.cpp:60: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]
60 | for(int i = 0; i < v[dg].size(); ++i) {
| ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 1; i < ve.size(); ++i) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
14160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
14160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
14160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
6128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
14160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
14160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
