| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 780092 | 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,int par)
{
First[u] = ++DFStime;
for(int i = 1;i < 33;i++)
{
level[u][i] = level[level[u][i - 1]][i - 1];
}
for(auto v:w[u])
{
if(v.first == par)
{
continue;
}
dist[v.first] = dist[u] + v.second;
DFS(v.first,u);
}
End[u] = DFStime;
}
bool check(int u,int v)
{
return (First[u] <= First[v] and End[u] <= End[v]);
}
int LCA(int u,int v)
{
if(check(u,v))
{
return u;
}
if(check(v,u))
{
return v;
}
for(int i = 32;i >= 0;i--)
{
if(!check(level[u][i],v))
{
u = level[u][i];
}
}
return level[u][0];
}
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,0);
}
void edge(int u,int v)
{
if(u == v)
{
return;
}
int d = abs(dist[u] - dist[v]);
w2[u].push_back({v,d});
w2[v].push_back({u,d});
}
int virtual_tree(vector<int> &g)
{
sort(g.begin(),g.end(),[](int &i, int &j){return (First[i] < First[j]);});
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(),[](int &i, int &j){return (First[i] < First[j]);});
vector<int> s;
s.push_back(g[0]);
for(int i = 1;i < g.size();i++)
{
while(!check(s.back(),g[i]))
{
edge(s.back(),s[s.size() - 2]);
s.pop_back();
}
s.push_back(g[i]);
}
while(s.size() > 1)
{
edge(s.back(),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};
}
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;
}