#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
const int N = 1e5+23;
int n,m,l;
int a[N],b[N],t[N];
vector <pair<int,int>> g[N];
int rut[N],parent[N],komp[N];
int dep[N],mxdepdole[N];
int maxd[N];
vector <int> sad;
void dfs(int x,int par){
sad.push_back(x);
parent[x] = par;
mxdepdole[x] = dep[x];
for(auto f : g[x]){
int u = f.first;
if(u == par) continue;
komp[u] = komp[x];
dep[u] = dep[x]+f.second;
dfs(u,x);
mxdepdole[x] = max(mxdepdole[x],mxdepdole[u]);
}
}
void dfs1(int x,int par,int ostali){
maxd[x] = max(dep[x]+ostali,mxdepdole[x]-dep[x]);
for(auto f : g[x]){
int u = f.first;
if(u == par) continue;
dfs1(u,x,ostali);
}
}
int travelTime(int br1,int br2,int br3,int *jed,int *dva,int *tri){
n = br1;
m = br2;
l = br3;
for(int i = 0; i < m; i++){ a[i+1] = jed[i]+1; b[i+1] = dva[i]+1; t[i+1] = tri[i]; }
if(m == n-1) return 0;
for(int i = 1; i <= m; i++){
g[a[i]].push_back({b[i],t[i]});
g[b[i]].push_back({a[i],t[i]});
}
int cnt = 1;
vector <int> minmaxds;
for(int i = 1; i <= n; i++){
if(komp[i]) continue;
komp[i] = cnt;
rut[cnt] = i;
sad.clear();
dfs(i,0);
if(g[i].empty()){
maxd[i] = 0;
minmaxds.push_back(0);
cnt++;
continue;
}
vector <int> pref(g[i].size(),0),suf(g[i].size(),0);
for(int j = 0; j < g[i].size(); j++){
pref[j] = mxdepdole[g[i][j].first];
if(j > 0) pref[j] = max(pref[j],pref[j-1]);
}
for(int j = g[i].size()-1; j >= 0; j--){
suf[j] = mxdepdole[g[i][j].first];
if(j < g[i].size()-1) suf[j] = max(suf[j],suf[j+1]);
}
for(int j = 0; j < g[i].size(); j++){
int u = g[i][j].first;
int ost = 0;
if(j > 0) ost = max(ost,pref[j-1]);
if(j < g[i].size()-1) ost = max(ost,suf[j+1]);
dfs1(u,i,ost);
}
maxd[i] = mxdepdole[i];
int minmaxd = 2e9;
for(auto f : sad) minmaxd = min(minmaxd,maxd[f]);
assert(minmaxd < 2e9 && minmaxd > 0);
minmaxds.push_back(minmaxd);
cnt++;
}
cnt--;
assert(cnt == n-m);
sort(minmaxds.begin(),minmaxds.end());
vector <int> v;
int maxi = -1,koji = -1;
for(int i = 0; i < minmaxds.size()-1; i++){
v.push_back(l+minmaxds.back()+minmaxds[i]);
if(minmaxds[i] > maxi){
maxi = minmaxds[i];
koji = i;
}
}
for(int i = 0; i < minmaxds.size()-1; i++){
if(i == koji) continue;
v.push_back(2*l+maxi+minmaxds[i]);
}
sort(v.begin(),v.end());
return v.back();
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j = 0; j < g[i].size(); j++){
| ~~^~~~~~~~~~~~~
dreaming.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(j < g[i].size()-1) suf[j] = max(suf[j],suf[j+1]);
| ~~^~~~~~~~~~~~~~~
dreaming.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j = 0; j < g[i].size(); j++){
| ~~^~~~~~~~~~~~~
dreaming.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | if(j < g[i].size()-1) ost = max(ost,suf[j+1]);
| ~~^~~~~~~~~~~~~~~
dreaming.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i = 0; i < minmaxds.size()-1; i++){
| ~~^~~~~~~~~~~~~~~~~~~
dreaming.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i = 0; i < minmaxds.size()-1; i++){
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
14916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
14916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
8652 KB |
Output is correct |
| 2 |
Correct |
39 ms |
8668 KB |
Output is correct |
| 3 |
Correct |
34 ms |
8644 KB |
Output is correct |
| 4 |
Correct |
41 ms |
8772 KB |
Output is correct |
| 5 |
Correct |
42 ms |
8664 KB |
Output is correct |
| 6 |
Correct |
34 ms |
9592 KB |
Output is correct |
| 7 |
Correct |
35 ms |
8972 KB |
Output is correct |
| 8 |
Correct |
33 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
32 ms |
8632 KB |
Output is correct |
| 10 |
Correct |
32 ms |
8896 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 12 |
Correct |
12 ms |
6472 KB |
Output is correct |
| 13 |
Correct |
13 ms |
6556 KB |
Output is correct |
| 14 |
Correct |
12 ms |
6472 KB |
Output is correct |
| 15 |
Correct |
12 ms |
6472 KB |
Output is correct |
| 16 |
Correct |
14 ms |
6456 KB |
Output is correct |
| 17 |
Correct |
12 ms |
6212 KB |
Output is correct |
| 18 |
Correct |
13 ms |
6504 KB |
Output is correct |
| 19 |
Correct |
12 ms |
6496 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 22 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 23 |
Correct |
16 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
14916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
