#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
struct edge
{
long long ver,dist;
edge(){};
edge(int vi, long long di)
{
ver = vi;
dist = di;
}
};
struct Point
{
int x,y,d;
Point(){};
Point(int xi, int yi, int di)
{
x = xi;
y = yi;
d = di;
}
};
int n;
vector<edge> g[MAXN];
long long sub[MAXN],used[MAXN];
long long mind;
vector<long long> comp;
void clear_used()
{
for(int i = 0; i < n; i++) used[i] = 0;
}
void clear_g()
{
for(int i = 0; i < n; i++) g[i].clear();
}
void dfs_dp(int beg, long long gor)
{
used[beg] = 1;
long long maxch = max(sub[beg],gor);
mind = min(mind,maxch);
long long fir = 0, sec = 0;
for(edge nb : g[beg])
{
if(!used[nb.ver])
{
if(nb.dist+sub[nb.ver] >= fir)
{
sec = fir;
fir = nb.dist+sub[nb.ver];
}
else if(nb.dist+sub[nb.ver] >= sec)
{
sec = nb.dist+sub[nb.ver];
}
}
}
for(edge nb : g[beg])
{
if(!used[nb.ver])
{
long long new_gor = gor;
if(nb.dist+sub[nb.ver] == fir) new_gor = max(new_gor,sec);
else new_gor = max(new_gor,fir);
new_gor += nb.dist;
dfs_dp(nb.ver,new_gor);
}
}
}
void dfs(int beg)
{
used[beg] = 1;
for(edge nb : g[beg])
{
if(!used[nb.ver])
{
dfs(nb.ver);
sub[beg] = max(sub[beg],sub[nb.ver]+nb.dist);
}
}
}
Point sp[MAXN];
int idx,lead[MAXN],br[MAXN];
bool cmp(Point p1, Point p2)
{
return p1.d<p2.d;
}
int find_lead(int x)
{
if(lead[x]==x) return x;
return lead[x] = find_lead(lead[x]);
}
void union1(int x, int y)
{
if(br[x]<br[y])
{
br[y] += br[x];
lead[x] = y;
}
else
{
br[x] += br[y];
lead[y] = x;
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
n = N;
for(int i = 0; i < M; i++)
{
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
for(int i = 0; i < N; i++) if(!used[i]) dfs(i);
clear_used();
for(int i = 0; i < N; i++)
{
if(!used[i])
{
mind = 1e9+5;
dfs_dp(i,0);
comp.push_back(mind);
}
}
idx = 0;
for(int i = 0; i < comp.size(); i++)
{
for(int j = i+1; j < comp.size(); j++)
{
sp[idx] = {i,j,comp[i]+comp[j]+L};
idx++;
}
}
clear_used();
clear_g();
for(int i = 0; i < comp.size(); i++)
{
lead[i] = i;
br[i] = 1;
}
sort(sp,sp+idx,cmp);
for(int i = 0; i < idx; i++)
{
int x = sp[i].x;
int y = sp[i].y;
x = find_lead(x);
y = find_lead(y);
if(x != y)
{
g[sp[i].x].push_back({sp[i].y,sp[i].d});
g[sp[i].y].push_back({sp[i].x,sp[i].d});
union1(x,y);
}
}
///
memset(sub,0,sizeof(sub));
for(int i = 0; i < comp.size(); i++) if(!used[i]) dfs(i);
clear_used();
long long ans = 0;
for(int i = 0; i < comp.size(); i++)
{
if(!used[i])
{
mind = 1e9+5;
dfs_dp(i,0);
ans = max(ans,mind);
}
}
return ans;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:144:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
dreaming.cpp:146:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int j = i+1; j < comp.size(); j++)
| ~~^~~~~~~~~~~~~
dreaming.cpp:148:43: warning: narrowing conversion of '((comp.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + comp.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)j))) + ((__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)L))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
148 | sp[idx] = {i,j,comp[i]+comp[j]+L};
dreaming.cpp:154:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
dreaming.cpp:177:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int i = 0; i < comp.size(); i++) if(!used[i]) dfs(i);
| ~~^~~~~~~~~~~~~
dreaming.cpp:180:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
15472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
15472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
19920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
15472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
