#include "bits/stdc++.h"
#include "dreaming.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define first fi
#define second se
void dfs1(vector<pair<int, int>> adj[], vector<bool> &visited, int u)
{
if(visited[u])
return;
visited[u] = true;
for(auto v: adj[u])
{
dfs1(adj, visited, v.fi);
}
}
pair<int, int> extract_components(vector<pair<int, int>> adj[], int N)
{
vector<int> temp;
vector<bool> visited(N, false);
for(int i = 0; i<N; i++)
{
if(!visited[i])
{
dfs1(adj, visited, i);
temp.pb(i);
}
}
pair<int, int> res;
res.fi = temp[0], res.se = temp[1];
return res;
}
void depth(vector<pair<int, int>> adj[], vector<bool> visited, vector<int> &cnt, int u)
{
visited[u] = true;
for(auto v: adj[u])
{
if(!visited[v.fi])
{
cnt[v.fi] = cnt[u] + v.se;
depth(adj, visited, cnt, v.fi);
}
}
}
pair<int, int> diameter(vector<pair<int, int>> adj[], int N, int u)
{
int a = u, b, c;
int maxi = 0;
vector<bool> visited(N, false);
vector<int> cnt(N, 0);
depth(adj, visited, cnt, a);
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
b = i;
}
}
cnt.assign(N, 0);
visited.assign(N, false);
depth(adj, visited, cnt, b);
maxi = 0;
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
c = i;
}
}
return mp(b, c);
}
vector<int> bfs(vector<pair<int, int>> adj[], int N, pair<int, int> d)
{
int st = d.fi, en = d.se;
vector<bool> visited(N, false);
vector<int> parent(N, -1);
queue<int> q;
q.push(st);
visited[st] = true;
bool flag = true;
while(!q.empty()&&flag)
{
int u = q.front();
q.pop();
for(auto v: adj[u])
{
if(visited[v.fi])
continue;
visited[v.fi] = true;
parent[v.fi] = u;
q.push(v.fi);
if(v.fi==en)
flag = false;
}
}
vector<int> path;
while(parent[en]!=-1)
{
path.pb(en);
en = parent[en];
}
path.pb(st);
reverse(all(path));
return path;
}
int solve(vector<pair<int, int>> adj[], int N)
{
int a = 0, b;
int maxi = 0;
vector<bool> visited(N, false);
vector<int> cnt(N, 0);
depth(adj, visited, cnt, a);
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
b = i;
}
}
cnt.assign(N, 0);
visited.assign(N, false);
depth(adj, visited, cnt, b);
maxi = 0;
for(int i = 0; i<N; i++)
{
if(maxi<cnt[i])
{
maxi = cnt[i];
}
}
return maxi;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
vector<pair<int, int>> adj[N];
for(int i = 0; i<M; i++)
{
adj[A[i]].pb(mp(B[i], T[i]));
adj[B[i]].pb(mp(A[i], T[i]));
}
pair<int, int> comps = extract_components(adj, N);
int a = comps.fi, b = comps.se;
pair<int, int> d1 = diameter(adj, N, a);
pair<int, int> d2 = diameter(adj, N, b);
vector<int> path1, path2;
path1 = bfs(adj, N, d1);
path2 = bfs(adj, N, d2);
int len1 = int(path1.size());
int len2 = int(path2.size());
vector<bool> visited(N, false);
vector<int> cnt1(N, 0), cnt2(N, 0);
depth(adj, visited, cnt1, path1[0]);
depth(adj, visited, cnt2, path2[0]);
int n1 = path1[0], n2 = path2[0];
int dif = 1e8;
for(int i = 1; i<len1; i++)
{
if(abs(cnt1[path1[i]]-(cnt1[path1[len1-1]]-cnt1[path1[i]]))<dif)
{
dif = abs(cnt1[path1[i]]-(cnt1[path1[len1-1]]-cnt1[path1[i]]));
n1 = path1[i];
}
}
dif = 1e8;
for(int i = 1; i<len2; i++)
{
if(abs(cnt2[path2[i]]-(cnt2[path2[len2-1]]-cnt2[path2[i]]))<dif)
{
dif = abs(cnt2[path2[i]]-(cnt2[path2[len2-1]]-cnt2[path2[i]]));
n2 = path2[i];
}
}
/*for(auto elt: path1)
cout << elt << ' ';
cout << endl;
for(auto elt: path2)
cout << elt << ' ';
cout << endl;
cout << n1 << ' ' << n2 << endl;*/
adj[n1].pb(mp(n2, L));
adj[n2].pb(mp(n1, L));
int res = solve(adj, N);
return res;
}
Compilation message
dreaming.cpp: In function 'void dfs1(std::vector<std::pair<int, int> >*, std::vector<bool>&, int)':
dreaming.cpp:18:30: error: 'struct std::pair<int, int>' has no member named 'fi'
18 | dfs1(adj, visited, v.fi);
| ^~
dreaming.cpp: In function 'std::pair<int, int> extract_components(std::vector<std::pair<int, int> >*, int)':
dreaming.cpp:37:9: error: 'struct std::pair<int, int>' has no member named 'fi'
37 | res.fi = temp[0], res.se = temp[1];
| ^~
dreaming.cpp:37:27: error: 'struct std::pair<int, int>' has no member named 'se'
37 | res.fi = temp[0], res.se = temp[1];
| ^~
dreaming.cpp: In function 'void depth(std::vector<std::pair<int, int> >*, std::vector<bool>, std::vector<int>&, int)':
dreaming.cpp:46:23: error: 'struct std::pair<int, int>' has no member named 'fi'
46 | if(!visited[v.fi])
| ^~
dreaming.cpp:48:19: error: 'struct std::pair<int, int>' has no member named 'fi'
48 | cnt[v.fi] = cnt[u] + v.se;
| ^~
dreaming.cpp:48:36: error: 'struct std::pair<int, int>' has no member named 'se'
48 | cnt[v.fi] = cnt[u] + v.se;
| ^~
dreaming.cpp:49:40: error: 'struct std::pair<int, int>' has no member named 'fi'
49 | depth(adj, visited, cnt, v.fi);
| ^~
dreaming.cpp: In function 'std::vector<int> bfs(std::vector<std::pair<int, int> >*, int, std::pair<int, int>)':
dreaming.cpp:89:16: error: 'struct std::pair<int, int>' has no member named 'fi'
89 | int st = d.fi, en = d.se;
| ^~
dreaming.cpp:104:26: error: 'struct std::pair<int, int>' has no member named 'fi'
104 | if(visited[v.fi])
| ^~
dreaming.cpp:106:23: error: 'struct std::pair<int, int>' has no member named 'fi'
106 | visited[v.fi] = true;
| ^~
dreaming.cpp:107:22: error: 'struct std::pair<int, int>' has no member named 'fi'
107 | parent[v.fi] = u;
| ^~
dreaming.cpp:108:22: error: 'struct std::pair<int, int>' has no member named 'fi'
108 | q.push(v.fi);
| ^~
dreaming.cpp:109:18: error: 'struct std::pair<int, int>' has no member named 'fi'
109 | if(v.fi==en)
| ^~
dreaming.cpp:109:22: error: 'en' was not declared in this scope; did you mean 'yn'?
109 | if(v.fi==en)
| ^~
| yn
dreaming.cpp:115:18: error: 'en' was not declared in this scope; did you mean 'yn'?
115 | while(parent[en]!=-1)
| ^~
| yn
dreaming.cpp:122:13: error: 'all' was not declared in this scope
122 | reverse(all(path));
| ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:168:19: error: 'struct std::pair<int, int>' has no member named 'fi'
168 | int a = comps.fi, b = comps.se;
| ^~
dreaming.cpp:171:42: error: 'b' was not declared in this scope
171 | pair<int, int> d2 = diameter(adj, N, b);
| ^
