| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 574211 | groshi | Factories (JOI14_factories) | 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<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include "factories.h"
using namespace std;
struct wi{
vector<int> Q;
vector<int> nowy;
int pre=0,post=0;
int rodzaj=0;
long long suma[21];
int t[21];
int poz=0;
long long dp[3];
bool byl=0;
}*w;
vector<pair<int,int> > mam,jedno;
vector<int> pomoc;
int pree=1,postt=1;
void dodaj(int x)
{
for(int i=1;i<=20;i++)
{
w[x].t[i]=w[w[x].t[i-1]].t[i-1];
w[x].suma[i]=w[x].suma[i-1]+w[w[x].t[i-1]].suma[i-1];
}
}
void dfs(int x,int ojc)
{
w[x].pre=pree;
pree++;
for(int i=0;i<w[x].Q.size();i+=2)
{
int pom=w[x].Q[i];
if(pom==ojc)
continue;
w[pom].t[0]=x;
w[pom].suma[0]=w[x].Q[i+1];
w[pom].poz=w[x].poz+1;
dodaj(pom);
dfs(pom,x);
}
w[x].post=postt;
postt++;
}
long long wynik=1e18;
void dfs2(int x,int ojc)
{
//cout<<x<<" "<<ojc<<"\n";
w[x].dp[1]=1e18;
w[x].dp[2]=1e18;
for(int i=0;i<w[x].nowy.size();i+=2)
{
int pom=w[x].nowy[i];
if(pom==ojc)
continue;
dfs2(pom,x);
w[x].dp[1]=min(w[x].dp[1],w[pom].dp[1]+w[x].nowy[i+1]);
w[x].dp[2]=min(w[x].dp[2],w[pom].dp[2]+w[x].nowy[i+1]);
}
w[x].dp[w[x].rodzaj]=0;
wynik=min(wynik,w[x].dp[1]+w[x].dp[2]);
}
pair<int,int> lca(int x,int y)
{
if(w[x].poz>w[y].poz)
swap(x,y);
long long wynik=0;
for(int i=20;i>=0;i--)
if(w[w[y].t[i]].poz>=w[x].poz)
{
wynik+=w[y].suma[i];
y=w[y].t[i];
}
if(x==y)
return {wynik,x};
for(int i=20;i>=0;i--)
if(w[x].t[i]!=w[y].t[i])
{
wynik+=w[x].suma[i];
wynik+=w[y].suma[i];
x=w[x].t[i];
y=w[y].t[i];
}
if(x==y)
return {wynik,x};
else return {wynik+w[x].suma[0]+w[y].suma[0],w[x].t[0]};
}
void init(int n,vector<int> a,vector<int> b,vector<int> c)
{
int x,y,z;
w=new wi[n+3];
for(int i=1;i<n;i++)
{
x=a[i-1];
y=b[i-1];
z=c[i-1];
w[x].Q.push_back(y);
w[y].Q.push_back(x);
w[x].Q.push_back(z);
w[y].Q.push_back(z);
}
dfs(0,-1);
}
long long Query(int S,vector<int> a,int T,vector<int> b)
{
int x;
wynik=1e18;
mam.clear();
pomoc.clear();
jedno.clear();
for(int i=1;i<=S;i++)
{
x=a[i-1];
w[x].rodzaj=1;
jedno.push_back({w[x].pre,x});
w[x].nowy.clear();
}
for(int i=1;i<=T;i++)
{
x=b[i-1];
w[x].rodzaj=2;
jedno.push_back({w[x].pre,x});
w[x].nowy.clear();
}
sort(jedno.begin(),jedno.end());
int mam=jedno.size();
for(int i=0;i<mam-1;i++)///+/-
{
pair<int,int> jest=lca(jedno[i].second,jedno[i+1].second);
jedno.push_back({w[jest.second].pre,jest.second});
}
sort(jedno.begin(),jedno.end());
pomoc.push_back(jedno[0].second);
//cout<<"zyje\n";
w[jedno[0].second].byl=1;
for(int i=1;i<jedno.size();i++)
{
x=jedno[i].second;
if(w[x].byl==1)
continue;
w[x].byl=1;
// cout<<"mam "<<x<<"\n";
while(pomoc.size()>0 && w[x].post>w[pomoc.back()].post)
pomoc.pop_back();
//if(pomoc.size()==0)
//cout<<"zle\n";
//cout<<"krawedz "<<pomoc.back()<<" "<<x<<" ";
int odl=lca(pomoc.back(),x).first;
//cout<<odl<<"\n";
w[pomoc.back()].nowy.push_back(x);
w[x].nowy.push_back(pomoc.back());
w[pomoc.back()].nowy.push_back(odl);
w[x].nowy.push_back(odl);
pomoc.push_back(x);
}
dfs2(jedno[0].second,-1);
//cout<<"koniec\n";
for(int i=0;i<jedno.size();i++)
{
w[jedno[i].second].nowy.clear();
w[jedno[i].second].dp[1]=1e18;
w[jedno[i].second].dp[2]=1e18;
w[jedno[i].second].byl=0;
w[jedno[i].second].rodzaj=0;
}
return wynik;
}