#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define F first
#define S second
#define siz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define EB emplace_back
#define MP make_pair
#define PF push_front
#define PB push_back
#define POB pop_back
#define POF pop_front
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define kiyohime ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
#define debug(...) cerr<<#__VA_ARGS__<<" = ";dbg(__VA_ARGS__);
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using vec = vector<T>;
template<typename T> using Prior = priority_queue<T>;
template<typename T> using prior = priority_queue<T, vec<T>, greater<T>>;
const int INF = 1e9 + 1;
const ll LLINF = (ll)4*1e18;
const ll MOD = 1e9+7;
const double PI = 3.14159265358;
const double EPS = 1e-8;
const int xx[8] = {0,1,0,-1,1,1,-1,-1};
const int yy[8] = {1,0,-1,0,1,-1,-1,1};
template<typename T> void dbg(T x){ cerr<<x<<endl; }
template<typename T, typename ...A> void dbg(T x, A ...y){ cerr<<x<<", "; dbg(y...);}
template <typename T>
void printv(vec<T> v, char c = ' ') {
bool spc = false;
for(auto i:v)
if(spc) cout << c << i;
else cout << i, spc = true;
cout << endl;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> void amax(T &a, T b) {if(a < b) a = b;}
template<typename T> void amin(T &a, T b) {if(a > b) a = b;}
void pmod(ll &a, ll b) {a = (a+b)%MOD;}
void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;}
void tmod(ll &a, ll b) {a = (a*b)%MOD;}
void UNI(vec<int> &v) {sort(ALL(v)); v.rs(unique(ALL(v))-v.begin());}
int getint() {int ret; cin >> ret; return ret;}
ll POW(ll a, ll b) {ll res=1; do{if(b%2)tmod(res,a);tmod(a,a);}while(b>>=1); return res;}
ll getll() {ll ret; cin >> ret; return ret;}
const int MXN = 1000000;
const int N = MXN + 10;
vec<pii> g[N];
int vis[N], par[N], dep[N];
int dis, pt;
void dfs(int x, int p, int v){
par[x] = p;
dep[x] = v;
vis[x] = true;
for(auto i:g[x]) if(i.F != p)
dfs(i.F, x, v + i.S);
if(v > dis) pt = x;
amax(dis, v);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]){
rep(i, m){
g[a[i]].EB(b[i], t[i]);
g[b[i]].EB(a[i], t[i]);
}
vec<int> v;
int self = 0;
rep(i, n) if(!vis[i]){
dis = pt = -1;
dfs(i, -1, 0);
dis = -1;
dfs(pt, -1, 0);
int idx = pt, len = INF;
while(~idx) {
amin(len, max(dep[idx], dis - dep[idx]));
idx = par[idx];
}
v.EB(len);
amax(self, len);
}
sort(ALL(v), greater<int>());
if(siz(v) == 1)
return self;
else
return max(self, v[0] + v[1] + l);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
34296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
34296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
34296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
28024 KB |
Output is correct |
| 2 |
Incorrect |
51 ms |
28056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
34296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
34296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
