| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 574212 | groshi | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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,int a[],int b[],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,int a[],int T,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;
}