| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 878517 | cpptowin | 공장들 (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"factories.h"
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define pb emplace_back
#define inf 1000000000
#define pii pair<long long ,long long >
#define vii vector<pii>
#define vi vector<long long >
using namespace std;
vii ke[maxn];
long long par[maxn][20],sz[maxn],h[maxn],d[maxn];
long long ind[maxn],head[maxn],cnt = 1;
vector<array<long long ,3>> adj[maxn];
bool type[maxn];
void dfs(long long u,long long parent)
{
sz[u] = 1;
for(auto [v,w] : ke[u])
{
if(v == parent) continue;
par[v][0] = u;
h[v] = h[u] + 1;
d[v] = d[u] + w;
dfs(v,u);
sz[u] += sz[v];
}
}
void hld(long long u,long long parent)
{
if(head[cnt] == 0) head[cnt] = u;
ind[u] = cnt;
long long sc = -1,maxx = -1;
for(auto [v,w] : ke[u]) if(v != parent)
{
if(maxx < sz[v])
{
maxx = sz[v];
sc = v;
}
}
if(sc != -1) hld(sc,u);
for(auto [v,w] : ke[u]) if(v != parent and v != sc)
{
cnt++;
hld(v,u);
}
}
void get(long long u)
{
long long val = d[u],t = type[u];
long long uchain,vchain = ind[1];
while(1)
{
uchain = ind[u];
adj[uchain].push_back({u,val,t});
if(uchain == vchain) return;
u = ind[u];
u = par[head[u]][0];
}
}
void Init(long long N,long long A[],long long B[],long long D[])
{
fo(i,0,N - 2)
{
ke[A[i] + 1].pb(B[i] + 1,D[i]);
ke[B[i] + 1].pb(A[i] + 1,D[i]);
}
dfs(1,1);
hld(1,1);
}
long long Query(long long S, long long X[], long long T, long long Y[])
{
long long ans = 2e18;
fo(i,0,S - 1) get(X[i] + 1);
fo(i,0,T - 1)
{
type[Y[i] + 1] = 1;
get(Y[i] + 1);
}
fo(i,1,cnt)
{
long long minn[2];
minn[0] = minn[1] = 2e18;
sort(adj[i].begin(),adj[i].end(),[](array<long long ,3> a,array<long long ,3> b)
{
return d[a[0]] > d[b[0]];
});
for(auto [v,dist,t] : adj[i])
{
ans = min(ans,minn[1 - t] - 2 * d[v] + dist);
minn[t] = min(minn[t],dist);
}
}
return ans;
}