#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
int n;
int dp[100001],dp1[100001];
vector<pair<int,int>>tr[100001];
bool vis[100001];
map<dos,int>ga;
int solve(int node,int p)
{
//debug(node);
int fat=0;
vis[node]=1;
for(auto it:tr[node])
{
if(it.first!=p)
{
fat=max(fat,it.second+solve(it.first,node));
}
}
return dp[node]=fat;
}
int sol=0;
int ans;
set<int>kal;
void solve1(int node,int p,int besti)
{
debug(node);
dp1[node]=max(dp[node],besti);
ans=min(dp1[node],ans);
set<pair<int,int>>gg,gg1;
for(auto it:tr[node])
{
if(it.first!=p)
{
gg.insert({-(dp[it.first]+it.second),it.first});
}
}
gg1=gg;
for(auto it:gg)
{
int p1=besti;
int p2=0;
auto u=it;
gg1.erase(it);
if(gg1.size()>0)
{
auto k =(*gg1.begin());
p2=-k.first;
}
//debug(u.second);
if(u.second>=0 && u.second<n && u.second!=p)solve1(u.second,node,max(p1,p2)+ga[{min(node,u.second),max(node,u.second)}]);
gg1.insert(u);
}
return;
}
int besti=0;
int far=0;
int nodi=0;
void dfs(int node,int p)
{
vis[node]=1;
if(far>besti)
{
besti=far;
nodi=node;
}
for (auto it:tr[node])
{
if(it.first!=p)
{
far+=it.second;
dfs(it.first,node);
far-=it.second;
}
}
}
void dfs1(int node,int p)
{
if(far>besti)
{
besti=far;
nodi=node;
}
for (auto it:tr[node])
{
if(it.first!=p)
{
far+=it.second;
dfs1(it.first,node);
far-=it.second;
}
}
}
int diameter(int root)
{
besti=0;
dfs(root,-1);
besti=0;
dfs1(nodi,-1);
return besti;
}
int step()
{
int ans=0;
memset(vis,0,sizeof vis);
for (int i = 0; i < n; ++i)
{
if(!vis[i])
{
ans=max(ans,diameter(i));
}
}
return ans;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
//flash;
n=N;
//debug(n);
ans=pow(10,9);
for (int i = 0; i < M; ++i)
{
int x=A[i];
int y=B[i];
int z=T[i];
//debugs(x,y);
tr[x].pb({y,z});
tr[y].pb({x,z});
ga[{min(x,y),max(x,y)}]=z;
}
sol=max(step(),sol);
memset(vis,0,sizeof vis);
for (int i = 0; i < n; ++i)
{
if(!vis[i])
{
solve(i,-1);
solve1(i,-1,0);
kal.insert(-ans);
ans=pow(10,9);
}
}
if(kal.size()>1)
{
auto u=(*kal.begin());
kal.erase(u);
auto k=(*kal.begin());
sol=max(-u+L+-k,sol);
}
if(kal.size()>1)
{
auto u=(*kal.begin());
kal.erase(u);
auto k=(*kal.begin());
sol=max(-u+L*2+-k,sol);
}
return sol;
}
//code the AC sol !
// BS/queue/map
Compilation message
dreaming.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
dreaming.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
30968 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
30968 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
30968 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1050 ms |
9568 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
30968 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
30968 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
