| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 780069 | CESxRhino | Factories (JOI14_factories) | 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 "factories.h"
#define ii pair<int,int>
#define f first
#define s second
#define pb push_back
#define int long long
#define endl '\n'
using namespace std;
int par[200005];
int depth[200005];
const int MAXN = 1e18;
vector<ii> w[200005];
vector<ii> w2[200005];
int level[200005][33];
int First[200005];
int End[200005];
int dist[200005];
int DFStime = 0;
int color[200005];
int s[200005];
int t[200005];
int mindist;
void DFS(int u)
{
First[u] = ++DFStime;
for(auto v:w[u])
{
if(v.first == level[u][0])
{
continue;
}
depth[v.first] = depth[u] + 1;
dist[v.first] = dist[u] + v.second;
level[v.first][0] = u;
for(int i = 1;i < 33;i++)
{
level[v.first][i] = level[level[v.first][i - 1]][i - 1];
}
DFS(v.first);
}
End[u] = DFStime;
}
int LCA(int u,int v)
{
if(depth[u] != depth[v])
{
if(depth[u] < depth[v])
{
swap(u,v);
}
int k = depth[u] - depth[v];
for(int i = 0;(1 << i) <= k;i++)
{
if(k >> i & 1)
{
u = level[u][i];
}
}
}
if(u == v)
{
return u;
}
int k = __lg(depth[u]);
for(int i = k;i >= 0;i--)
{
if(level[u][i] != level[v][i])
{
u = level[u][i];
v = level[v][i];
}
}
return level[u][0];
}
bool cmp(int i,int j)
{
return First[i] < First[j];
}
bool check(int u,int v)
{
return (First[u] <= First[v] and End[u] <= End[v]);
}
int virtual_tree(vector<int> &g)
{
sort(g.begin(),g.end(),cmp);
for(int i = (int) (g.size()) - 2;i >= 0;i--)
{
int res = LCA(g[i],g[i + 1]);
g.push_back(res);
}
sort(g.begin(),g.end(),cmp);
vector<int> s;
s.push_back(g[0]);
for(int i = 1;i < g.size();i++)
{
int v = g[i];
while(s.size() >= 2 and !check(s.back(),v))
{
w2[s[s.size() - 2]].push_back(ii(s.back(),abs(dist[s.back()] - dist[s[s.size() - 2]])));
w2[s.back()].push_back(ii(s[s.size() - 2],abs(dist[s.back()] - dist[s[s.size() - 2]])));
s.pop_back();
}
s.push_back(v);
}
while(s.size() >= 2)
{
w2[s[s.size() - 2]].push_back(ii(s.back(),abs(dist[s.back()] - dist[s[s.size() - 2]])));
w2[s.back()].push_back(ii(s[s.size() - 2],abs(dist[s.back()] - dist[s[s.size() - 2]])));
s.pop_back();
}
return s[0];
}
ii DFS2(int u,int par)
{
int min1 = MAXN;
int min2 = MAXN;
if(color[u] == 1)
{
min1 = 0;
}
else if(color[u] == 2)
{
min2 = 0;
}
for(auto v:w2[u])
{
if(v.first != par)
{
ii tree = DFS2(v.first,u);
min1 = min(min1,v.second + tree.first);
min2 = min(min2,v.second + tree.second);
}
}
mindist = min(mindist,min1 + min2);
return {min1,min2};
}
void Init(int n, int a[], int b[], int d[])
{
for(int i = 0;i < n - 1;i++)
{
w[a[i]].pb({b[i],d[i]}),
w[b[i]].pb({a[i],d[i]});
}
DFS(0);
}
long long Query(int n, int x[], int m, int y[])
{
vector<int> g;
for(int i = 0;i < n;i++)
{
g.push_back(x[i]);
color[x[i]] = 1;
}
for(int i = 0;i < n;i++)
{
g.push_back(y[i]);
color[y[i]] = 2;
}
int r = virtual_tree(g);
mindist = 1e18;
DFS2(r,r);
for(auto x:g)
w2[x].clear(),
color[x] = 0;
return mindist;
}