| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 897390 | Muhammad_Aneeq | Dreaming (IOI13_dreaming) | C++17 | 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 <vector>
#include <algorithm>
using namespace std;
int const N=1e5+10;
vector<pair<int,int>>nei[N]={};
vector<int>heads;
bool vis[N]={};
int cost[N]={};
void dfs(int n)
{
vis[n]=1;
for (auto [i,w]:nei[n])
{
if (!vis[i])
{
cost[n]+=w;
dfs(i);
cost[n]+=cost[i];
}
}
}
vector<pair<int,int>>cur={};
void getroot(int n,int pa,int root)
{
int f=0;
for (auto [i,w]:nei[n])
{
if (i!=pa)
{
f=max(f,cost[i]);
getroot(i,n,root);
}
else
f=max(f,cost[pa]-cost[n]);
}
cur.push_back({f,n});
}
void dfs1(int n,int m=-1)
{
for (auto [i,w]:nei[n])
if (i!=m)
{
cost[i]+=cost[n];
cost[i]+=w;
dfs1(i,n);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for (int i=0;i<m;i++)
{
nei[a[i]].push_back({b[i],t[i]});
nei[b[i]].push_back({a[i],t[i]});
}
for (int i=0;i<n;i++)
{
if (!vis[i])
{
heads.push_back(i);
dfs(i);
}
}
for (int i=0;i<n;i++)
vis[i]={};
vector<pair<int,int>>new_head;
for (auto i:heads)
{
getroot(i,-1,i);
sort(begin(cur),end(cur));
new_head.push_back(cur[0]);
cur={};
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
for (int i=1;i<new_head.size();i++)
{
nei[new_head[0].second].push_back({new_head[i].second,l});
nei[new_head[i].second].push_back({new_head[0].second,l});
}
for (int i=0;i<n;i++)
cost[i]=0;
dfs1(0);
new_head={};
for (int i=0;i<n;i++)
{
new_head.push_back({cost[i],i});
cost[i]=0;
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
dfs1(new_head[0].second);
new_head={};
for (int i=0;i<n;i++)
{
new_head.push_back({cost[i],i});
cost[i]=0;
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
return new_head[0].first;
}