| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 412916 | LouayFarah | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
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 "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;
}