#include "dreaming.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"\"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxn=1e5+10;
int n,m,l;
int p[mxn];
vector<pii> adj[mxn];
vector<int> root;
vector<int> farth[2];
int dist[2][2][mxn];
int findp(int x) {
while(p[x]!=x) p[x]=p[p[x]],x=p[x];
return x;
}
void unionset(int u,int v) {
int U=findp(u),V=findp(v);
p[U]=V;
}
int dep[mxn];
void solve(int u,int ii) {
memset(dep,-1,sizeof(dep));
queue<pii> q;
q.push({u,0});
int mx=0,idx=-1;
while(!q.empty()) {
pii cur=q.front(); q.pop();
int u=cur.first,d=cur.second;
dep[u]=d;
if(dep[u]>mx) {
mx=dep[u]; idx=u;
}
for(auto vw:adj[u]) {
if(dep[vw.first]==-1) {
dep[vw.first]=d+vw.second;
q.push({vw.first,dep[vw.first]});
}
}
}
farth[ii].push_back(idx);
int mx2=0,idx2=-1;
memset(dep,-1,sizeof(dep));
queue<pii> q2;
q2.push({idx,0});
while(!q2.empty()) {
pii cur=q2.front(); q2.pop();
int u=cur.first,d=cur.second;
dep[u]=d;
if(dep[u]>mx2) {
mx2=dep[u];
idx2=u;
}
for(auto vw:adj[u]) {
int v=vw.first,w=vw.second;
if(dep[v]==-1) {
dep[v]=d+w;
q2.push({v,dep[v]});
}
}
}
farth[ii].push_back(idx2);
}
void finddist(int ii,int jj) {
memset(dist[ii][jj],-1,sizeof(dist[ii][jj]));
queue<pii> q;
q.push({farth[ii][jj],0});
while(!q.empty()) {
pii cur=q.front(); q.pop();
int u=cur.first,d=cur.second;
dist[ii][jj][u]=d;
for(auto vw:adj[u]) {
int v=vw.first,w=vw.second;
if(dist[ii][jj][v]==-1) {
dist[ii][jj][v]=d+w;
q.push({v,d+w});
}
}
}
}
vector<int> group[2];
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N,m=M,l=L;
for(int i=0;i<n;i++) p[i]=i;
for(int i=0;i<m;i++) {
unionset(A[i],B[i]);
adj[A[i]].push_back({B[i],T[i]});
adj[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<n;i++) {
p[i]=findp(p[i]);
root.push_back(p[i]);
}
sort(all(root));
root.erase(unique(all(root)),root.end());
assert(root.size()>1);
for(int i=0;i<2;i++) {
solve(root[i],i);
// debug(farth[i]);
}
for(int i=0;i<2;i++) {
for(int j=0;j<2;j++) {
finddist(i,j);
}
}
for(int i=0;i<n;i++) {
if(p[i]==root[0]) group[0].push_back(i);
else group[1].push_back(i);
}
int mn=INF;
for(auto u:group[0]) {
mn=min(mn,max(dist[0][0][u],dist[0][1][u]));
}
int mn2=INF;
for(auto u:group[1]) {
mn2=min(mn2,max(dist[1][0][u],dist[1][1][u]));
}
return mn+mn2+l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
11204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
11204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
8852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
11204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
