#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]);
minmaxds.push_back(minmaxd);
cnt++;
}
cnt--;
assert(cnt == n-m);
sort(minmaxds.begin(),minmaxds.end());
assert(minmaxds.size() == 2);
if(minmaxds.size() == 2){
return minmaxds[0]+l+minmaxds[1];
}
}
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:55:18: warning: control reaches end of non-void function [-Wreturn-type]
55 | vector <int> minmaxds;
| ^~~~~~~~
/usr/bin/ld: /tmp/ccawj14k.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
