#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN = 1e5 + 10;
vector < pair < int, int > > g[MAXN];
int mark[MAXN];
int used[MAXN];
void dfs0(int beg, int par)
{
mark[beg] = 1;
used[beg] = 1;
int nb;
for (int i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i].first;
if(nb != par)
dfs0(nb);
}
}
int far = 0, far_index = 0;
void dfs_diam(int beg, int par, int to_there)
{
if(far <= to_there)
{
far = to_there;
far_index = beg;
}
used[beg] = 1;
int nb, distt;
for (int i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i].first;
distt = g[beg][i].second;
if(nb != par)dfs_diam(nb, beg, to_there + distt);
}
}
int maxdist = 0;
int dfs(int beg, int par)
{
used[beg] = 1;
int nb, distt;
int maxx = 0;
for (int i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i].first;
distt = g[beg][i].second;
if(nb != par)maxx = max(maxx, dfs(nb, beg)+distt);
}
return maxx;
}
vector < pair < int, int > > path;
int st, fi;
int marked[MAXN];
int dfs_form(int beg, int par, int add)
{
marked[beg] = 1;
used[beg] = 1;
if(beg == fi)
{
path.push_back(make_pair(beg, add));
return 1;
}
int nb, distt;
int found = 0;
for (int i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i].first;
distt = g[beg][i].second;
if(nb != par)
{
if(dfs_form(nb, beg, add + distt))found = 1;
}
}
if(found)path.push_back(make_pair(beg, add));
return found;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i = 0; i < M; ++ i)
{
g[A[i]].push_back(make_pair(B[i], T[i]));
g[B[i]].push_back(make_pair(A[i], T[i]));
}
int n = N;
vector < pair < int/*diam*/, int > > pq;
for (int i = 0; i < n; ++ i)
{
if(marked[i])continue;
int aa1 = 0, bb1 = 0;
int aa2 = 0, bb2 = 0;
far = 0;
far_index = 0;
dfs_diam(i, -1, 0);
aa1 = far_index;
far = 0;
far_index = 0;
dfs_diam(aa1, -1, 0);
bb1 = far_index;
path.clear();
st = aa1;
fi = bb1;
dfs_form(st, -1, 0);
int index1 = path[0].first;
int total1 = path[0].second;
int best1 = total1, curr;
for (int j = 1; j < path.size(); ++ j)
{
curr = max(path[j].second, total1 - path[j].second);
if(curr < best1)
{
best1 = curr;
index1 = path[j].first;
}
}
pq.push_back(make_pair(best1, index1));
// cout << "component " << best1 << " " << index1 << endl;
}
sort(pq.begin(), pq.end());
int sz = pq.size();
int diam1, ii1;
int diam2, ii2;
int neww;
for (int i = pq.size()-1; i >= 1; -- i)
{
diam1 = pq[i].first;
ii1 = pq[i].second;
diam2 = pq[i-1].first;
ii2 = pq[i-1].second;
neww = max(max(diam1, diam2), min(diam1, diam2) + L);
g[ii1].push_back(make_pair(ii2, L));
g[ii2].push_back(make_pair(ii1, L));
if(diam1 > diam2)pq[i-1] = make_pair(neww, ii1);
else pq[i-1] = make_pair(neww, ii2);
}
int aa1 = 0, bb1 = 0;
int aa2 = 0, bb2 = 0;
far = 0;
far_index = 0;
dfs_diam(0, -1, 0);
aa1 = far_index;
return dfs(aa1);
}
Compilation message
dreaming.cpp: In function 'void dfs0(int, int)':
dreaming.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp:17:20: error: too few arguments to function 'void dfs0(int, int)'
17 | dfs0(nb);
| ^
dreaming.cpp:8:6: note: declared here
8 | void dfs0(int beg, int par)
| ^~~~
dreaming.cpp: In function 'void dfs_diam(int, int, int)':
dreaming.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs(int, int)':
dreaming.cpp:43:23: 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 < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs_form(int, int, int)':
dreaming.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:114:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int j = 1; j < path.size(); ++ j)
| ~~^~~~~~~~~~~~~
dreaming.cpp:93:13: warning: unused variable 'aa2' [-Wunused-variable]
93 | int aa2 = 0, bb2 = 0;
| ^~~
dreaming.cpp:93:22: warning: unused variable 'bb2' [-Wunused-variable]
93 | int aa2 = 0, bb2 = 0;
| ^~~
dreaming.cpp:160:19: error: too few arguments to function 'int dfs(int, int)'
160 | return dfs(aa1);
| ^
dreaming.cpp:38:5: note: declared here
38 | int dfs(int beg, int par)
| ^~~
dreaming.cpp:129:9: warning: unused variable 'sz' [-Wunused-variable]
129 | int sz = pq.size();
| ^~
dreaming.cpp:152:22: warning: unused variable 'bb1' [-Wunused-variable]
152 | int aa1 = 0, bb1 = 0;
| ^~~
dreaming.cpp:153:13: warning: unused variable 'aa2' [-Wunused-variable]
153 | int aa2 = 0, bb2 = 0;
| ^~~
dreaming.cpp:153:22: warning: unused variable 'bb2' [-Wunused-variable]
153 | int aa2 = 0, bb2 = 0;
| ^~~
