This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
int maksd;
const int N = 1e5 + 5;
int vidjen[N];
vector<vector<pair<int, int > > > g(N);
vector<int> v;
int mm, s;
vector<vector<pair<int, int> > > path(N);
void najdalji(int u, int pret, int d)
{
vidjen[u] = 1;
if(d>=mm)
{
mm = d;
s = u;
}
for(auto x : g[u])
{
if(x.first==pret) continue;
najdalji(x.first, u, x.second+d);
}
}
bool get_path(int u, int pret, int k, int parent, int d)
{
vidjen[u] = 1;
if(u==k)
{
path[parent].pb({u, d});
return true;
}
for(auto x : g[u])
{
if(x.first==pret) continue;
if(get_path(x.first, u, k, parent, x.second))
{
path[parent].pb({u, d});
return true;
}
}
return false;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for(int i = 0;i<m;i++)
{
int x = a[i];
int y = b[i];
int l = t[i];
g[x].pb({y, l});
g[y].pb({x, l});
}
for(int i = 0;i<n;i++)
{
if(vidjen[i]) continue;
mm = 0;
s = i;
int l1;
najdalji(i, -1, 0);
l1 = s;
mm = 0;
s = l1;
int l2;
najdalji(l1, -1, 0);
l2 = s;
get_path(l1, -1, l2, i, 0);
int sum = 0;
int c;
int mini = INF;
int m2 = 0;
int p = 0;
for(auto x : path[i]) sum += x.second;
for(auto x : path[i])
{
p += x.second;
if(abs(p - (sum - p)) < mini)
{
m2 = max(p, abs(sum - p));
mini = abs(p - abs((sum - p)));
c = x.first;
}
}
maksd = max(maksd, sum);
v.pb(m2);
}
sort(all(v), greater<int>());
int ans = maksd;
if(len(v)==1)
{
return ans;
}
ans = max(ans, v[0]+v[1]+l);
if(len(v)>=3)
{
ans = max(ans, v[1] + v[2] + 2*l);
}
return ans;
}
Compilation message (stderr)
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:86:13: warning: variable 'c' set but not used [-Wunused-but-set-variable]
86 | int c;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |