| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1286922 | Faisal_Saqib | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
// #include "factories.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll KP=1e6+100,NP=1e6+100,lg=22;
ll n,in[KP],out[KP];
bool iny[KP],inx[KP];
vector<pair<ll,ll>> ma[KP];
ll h[KP];
pair<ll,ll> mi[NP][lg];
vector<ll> ord;
void dfs(ll x,ll p=-1)
{
in[x]=ord.size();
ord.push_back(x);
for(auto y:ma[x])
{
if(y.second!=p)
{
h[y.second]=h[x]+y.first;
dfs(y.second,x);
ord.push_back(x);
}
}
out[x]=ord.size();
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
ord.clear();
for(ll i=0;i<=n;i++)h[i]=0,ma[i].clear();
for(ll i=0;i<n-1;i++)
{
ma[A[i]].push_back({D[i],B[i]});
ma[B[i]].push_back({D[i],A[i]});
}
dfs(0);
cout<<"H: ";
for(ll i=0;i<ord.size();i++)
{
mi[i][0]={h[ord[i]],ord[i]};
cout<<h[ord[i]]<<' ';
}
cout<<endl;
for(ll j=1;j<lg;j++)
{
for(ll i=0;i+(1<<j)-1<ord.size();i++)
{
mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
}
// cout<<ord.size()<<endl;
// ord.size() = 2*n-1
}
pair<ll,ll> getmin(ll x,ll y)
{
if(x>y)swap(x,y);
// [x,y]
ll lp=__lg(y-x+1);
// cout<<"Getting min "<<x<<' '<<y<<' '<<min(mi[x][lp],mi[y-(1<<lp)+1][lp]).second<<endl;
return min(mi[x][lp],mi[y-(1<<lp)+1][lp]);
}
vector<pair<int,int>> cur;
ll dp[KP][2],ans=1e18;
void dfsp(int x,int p=-1)
{
dp[x][0]=dp[x][1]=1e18;
if(inx[x])
{
dp[x][0]=h[x];
inx[x]=0;
}
if(iny[x])
{
dp[x][1]=h[x];
iny[x]=0;
}
while(cur.size()>0)
{
int y=cur.back().second;
if(in[x]<=in[y] and out[y]<=out[x])
{
cur.pop_back();
dfsp(y,x);
dp[x][0]=min(dp[x][0],dp[y][0]);
dp[x][1]=min(dp[x][1],dp[y][1]);
}
else
{
break;
}
}
ans=min(ans,dp[x][0]+dp[x][1]-2*h[x]);
}
long long Query(int S, int X[], int T, int Y[]) {
cur.clear();
ans=1e18;
for(int i=0;i<S;i++)
{
inx[X[i]]=1;
cur.push_back({in[X[i]],X[i]});
}
for(int i=0;i<T;i++)
{
iny[Y[i]]=1;
cur.push_back({in[Y[i]],Y[i]});
}
sort(begin(cur),end(cur));
// cout<<cur.size()<<endl;
int sz=cur.size();
for(int i=1;i<sz;i++)
{
// cout<<"Getting lca "<<cur[i].second<<' '<<cur[i-1].second<<' ';
int x=getmin(in[cur[i].second],in[cur[i-1].second]).second;
// cout<<x<<endl;
cur.push_back({in[x],x});
}
sort(rbegin(cur),rend(cur));
// do dfs using cur
cur.resize(unique(begin(cur),end(cur))-begin(cur));
auto y=cur.back();
cur.pop_back();
dfsp(y.first);
return ans;
}