#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const long long MAXN = 5e5 + 10;
vector < pair < long long, long long > > g[MAXN];
long long mark[MAXN];
long long used[MAXN];
void dfs0(long long beg)
{
mark[beg] = 1;
used[beg] = 1;
long long nb;
for (long long i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i].first;
if(!used[nb])
dfs0(nb);
}
}
long long far = 0, far_index;
void dfs_diam(int beg, 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(!used[nb])dfs_diam(nb, to_there + distt);
}
}
long long maxdist = 0;
long long dfs(long long beg)
{
used[beg] = 1;
long long nb, distt;
long long maxx = 0;
for (long long i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i].first;
distt = g[beg][i].second;
if(!used[nb])maxx = max(maxx, dfs(nb)+distt);
}
return maxx;
}
vector < pair < long long, long long > > path;
long long st, fi;
long long dfs_form(long long beg, long long add)
{
used[beg] = 1;
if(beg == fi)
{
path.push_back(make_pair(beg, add));
return 1;
}
long long nb, distt;
long long found = 0;
for (long long i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i].first;
distt = g[beg][i].second;
if(!used[nb])
{
if(dfs_form(nb, add + distt))found = 1;
}
}
if(found)path.push_back(make_pair(beg, add));
return found;
}
vector < pair < long long, long long > > path1, path2;
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (long long 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]));
}
long long n = N;
dfs0(0);
/// opit
int aa1 = 0, bb1 = 0;
int aa2 = 0, bb2 = 0;
memset(used, 0, sizeof(used));
far = 0;
far_index = 0;
dfs_diam(0, 0);
aa1 = far_index;
memset(used, 0, sizeof(used));
far = 0;
far_index = 0;
dfs_diam(aa1, 0);
bb1 = far_index;
int starter2 = 0;
for (int i = 0; i < n && (starter2 == -1); ++ i)
if(!mark[i])starter2 = i;
assert(starter2 != -1);
memset(used, 0, sizeof(used));
far = 0;
far_index = 0;
dfs_diam(starter2, 0);
aa2 = far_index;
memset(used, 0, sizeof(used));
far = 0;
far_index = 0;
dfs_diam(aa2, 0);
bb2 = far_index;
path.clear();
st = aa1;
fi = bb1;
dfs_form(st, 0);
memset(used, 0, sizeof(used));
path1 = path;
path.clear();
st = aa2;
fi = bb2;
memset(used, 0, sizeof(used));
dfs_form(st, 0);
path2 = path;
long long index1 = path1[0].first, index2 = path2[0].first;
long long total1 = path1[0].second;
long long total2 = path2[0].second;
long long best1 = total1, best2 = total2, curr;
for (int i = 1; i < path1.size(); ++ i)
{
curr = max(path1[i].second, total1 - path1[i].second);
if(curr < best1)
{
best1 = curr;
index1 = path1[i].first;
}
}
for (int i = 1; i < path2.size(); ++ i)
{
curr = max(path2[i].second, total2 - path2[i].second);
if(curr < best2)
{
best2 = curr;
index2 = path2[i].first;
}
}
g[index1].push_back(make_pair(index2, L));
g[index2].push_back(make_pair(index1, L));
long long ans = 0;
memset(used, 0, sizeof(used));
ans = max(ans, dfs(aa1));
memset(used, 0, sizeof(used));
ans = max(ans, dfs(bb1));
memset(used, 0, sizeof(used));
ans = max(ans, dfs(aa2));
memset(used, 0, sizeof(used));
ans = max(ans, dfs(bb2));
return ans;
///
}
Compilation message
dreaming.cpp: In function 'void dfs0(long long int)':
dreaming.cpp:13:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (long long i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs_diam(int, int)':
dreaming.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int dfs(long long int)':
dreaming.cpp:43:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (long long i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int dfs_form(long long int, long long int)':
dreaming.cpp:63:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (long long i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int i = 1; i < path1.size(); ++ i)
| ~~^~~~~~~~~~~~~~
dreaming.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int i = 1; i < path2.size(); ++ i)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
37992 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
42156 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
37992 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
