#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
int to,cost;
};
int n,m,l,a1[100005],a2[100005],a3[100005],used[100005],ma[100005],sma[100005],a,in[100005],otg[100005],costin[100005];
vector<cell>v[100005];
void dfs(int beg)
{
used[beg]=1;
int w;
for(int i=0;i<(int)(v[beg].size());i++)
{
w=v[beg][i].to;
if(!used[w])
{
dfs(w);
if(ma[beg]<ma[w]+v[beg][i].cost)
{
in[beg]=w;
costin[beg]=v[beg][i].cost;
sma[beg]=ma[beg];
ma[beg]=ma[w]+v[beg][i].cost;
}
else if(sma[beg]<ma[w]+v[beg][i].cost)
{
sma[beg]=ma[w]+v[beg][i].cost;
}
}
}
}
void find_ma(int beg,int izm,int par)
{
if(beg==par)return;
if(izm>ma[beg])
{
int g=izm;
g=min(izm,ma[par]);
otg[beg]=g;
return;
}
find_ma(in[beg],max(izm,sma[beg])+costin[beg],beg);
}
void fil(int beg)
{
int w;
used[beg]=1;
for(int i=0;i<(int)(v[beg].size());i++)
{
w=v[beg][i].to;
if(!used[w])
{
fil(w);
}
}
}
int travelTime(int n,int m,int l,int a1[],int a2[],int a3[])
//void read()
{
//cin>>n>>m>>l;
cell h;
for(int i=1;i<=m;i++)
{
//cin>>a1[i]>>a2[i]>>a3[i];
h.to=a2[i];
h.cost=a3[i];
v[a1[i]].push_back(h);
h.to=a1[i];
v[a2[i]].push_back(h);
}
for(int i=1;i<=n;i++)
{
if(!used[i])
{
dfs(i);
}
}
memset(used,0,sizeof(used));
for(int i=1;i<=n;i++)
{
if(!used[i])
{
find_ma(i,0,0);
fil(i);
}
}
sort(otg+1,otg+n+1);
//if(otg[n-2])cout<<max(otg[n],otg[n-2]+l)+otg[n-1]+l<<endl;
//else cout<<otg[n]+otg[n-1]+l;
if(otg[n-2])return max(otg[n],otg[n-2]+l)+otg[n-1]+l;
else return otg[n]+otg[n-1]+l;
}
/*int main()
{
speed();
read();
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
13284 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
13284 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
7964 KB |
Output is correct |
2 |
Correct |
18 ms |
8164 KB |
Output is correct |
3 |
Correct |
21 ms |
8124 KB |
Output is correct |
4 |
Correct |
17 ms |
8036 KB |
Output is correct |
5 |
Correct |
21 ms |
8064 KB |
Output is correct |
6 |
Correct |
20 ms |
8388 KB |
Output is correct |
7 |
Correct |
23 ms |
8224 KB |
Output is correct |
8 |
Correct |
15 ms |
8024 KB |
Output is correct |
9 |
Correct |
15 ms |
8028 KB |
Output is correct |
10 |
Correct |
15 ms |
8444 KB |
Output is correct |
11 |
Correct |
2 ms |
4956 KB |
Output is correct |
12 |
Correct |
4 ms |
6132 KB |
Output is correct |
13 |
Correct |
3 ms |
5980 KB |
Output is correct |
14 |
Correct |
3 ms |
5980 KB |
Output is correct |
15 |
Correct |
3 ms |
6004 KB |
Output is correct |
16 |
Correct |
3 ms |
5720 KB |
Output is correct |
17 |
Correct |
4 ms |
5212 KB |
Output is correct |
18 |
Correct |
4 ms |
5980 KB |
Output is correct |
19 |
Correct |
3 ms |
5724 KB |
Output is correct |
20 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
4956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
13284 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |