| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 362099 | denkendoemeer | 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 "factories.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool maxi(ll &a,ll b)
{
if (a<b)
return a=b,1;
return 0;
}
bool mini(ll &a,ll b)
{
if (a>b)
return a=b,1;
return 0;
}
struct ed
{
int to,w;
};
vector<ed>e[500005];
struct grup
{
int c;
ll d;
};
vector<grup>g[500005];
int sum[500005],ok[500005];
ll ans,b1[500005],b2[500005];
int dfs(int nod,int t=-1)
{
sum[nod]=1;
for(auto it:e[nod])
if (ok[it.to]==0 && it.to!=t)
sum[nod]+=dfs(it.to,nod);
return sum[nod];
}
int centr(int nod,int aux,int t=-1)
{
for(auto it:e[nod])
if (ok[it.to]==0 && it.to!=t)
if (sum[it.to]*2>=aux)
return centr(it.to,aux,nod);
return nod;
}
int auxi;
void dfs2(int nod,int t=-1,ll dist=0)
{
g[nod].push_back({auxi,dist});
for(auto it:e[nod])
if (ok[it.to]==0 && it.to!=t)
dfs2(it.to,nod,dist+it.w);
}
void calc(int nod)
{
int c=centr(nod,dfs(nod));
auxi=c;
dfs2(c);
ok[c]=1;
for(auto it:e[c])
if (ok[it.to]==0)
calc(it.to);
}
void Init(int n,int a[],int b[],int d[])
{
int i;
for(i=0;i<n-1;i++)
e[a[i]].push_back({b[i],d[i]}),e[b[i]].push_back({a[i],d[i]});
calc(0);
memset(b1,0x3f,sizeof(b1));
memset(b2,0x3f,sizeof(b2));
}
ll query(int s,int x[],int t,int y[])
{
ans=2e17;
int i;
for(i=0;i<s;i++)
for(auto it:g[x[i]])
mini(b2[it.c],it.d);
for(i=0;i<t;i++)
for(auto it:g[y[i]]){
mini(b1[it.c],it.d);
mini(ans,b1[it.c]+b2[it.c]);
}
for(i=0;i<s;i++)
for(auto it:g[x[i]])
b1[it.c]=b2[it.c]=2e17;
for(i=0;i<t;i++)
for(auto it:g[y[i]])
b1[it.c]=b2[it.c]=2e17;
return ans;
}