#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll maxN=2e6+10;
#define taskname "codeforce"
ll dp1[maxN],dp2[maxN],mn1[maxN],mn2[maxN];
const ll inf=1e15;
#define pli pair<ll,ll>
#define fi first
#define se second
vector<pli>g[maxN];
vector<pli>c[maxN];
ll vt[maxN];
void dfs1(ll u,ll p)
{
dp1[u]=inf;
mn1[u]=mn2[u]=inf;
for(auto vv:c[u])
{
ll v=vv.fi;
ll w=vv.se;
//if(v==p) {continue;}
dfs1(v,u);
dp1[u]=min(dp1[v]+w,dp1[u]);
if(dp1[v]+w<=mn1[u])
{
mn2[u]=mn1[u];
mn1[u]=dp1[v]+w;
}
else if(dp1[v]+w<=mn2[u])
{
mn2[u]=dp1[v]+w;
}
}
if(vt[u]>=2) dp1[u]=0;
}
void dfs2(ll u,ll p,ll w)
{
dp2[u]=inf;
if(vt[u]>=2) dp2[u]=0;
else
{
if(p!=0)
{
if(vt[p]>=2) dp2[u]=w;
else
{
if(dp1[u]+w==mn1[p]) dp2[u]=mn2[p]+w;
else dp2[u]=mn1[p]+w;
dp2[u]=min(dp2[u],dp2[p]+w);
}
}
}
for(auto vv:c[u])
{
ll v=vv.fi;
ll w=vv.se;
//if(v==p) continue;
dfs2(v,u,w);
}
}
#define pb push_back
ll in[maxN],out[maxN];
bool cmp(ll x,ll y)
{
return in[x]<in[y];
}
ll cnt[maxN];
ll h[maxN];
ll dd[maxN],tg=0;
ll par[maxN][21];
void dfs(ll u=0,ll p=0)
{
in[u]=++tg;
par[u][0]=p;
for(int i=1;i<=20;i++) par[u][i]=par[par[u][i-1]][i-1];
for(auto vv:g[u])
{
ll v=vv.fi;
ll w=vv.se;
if(v!=p)
{
h[v]=h[u]+1;
dd[v]=dd[u]+w;
dfs(v,u);
}
}
out[u]=tg;
}
ll LCA(ll u, ll v)
{
if(h[u]<h[v]) swap(u,v);
ll log=log2(h[u])+1;
for(int i=log;i>=0;i--)
{
if(h[par[u][i]]>=h[v]) u=par[u][i];
}
if(u==v) return u;
for(int i=log;i>=0;i--)
{
if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
}
return par[u][0];
}
ll dis(ll u,ll v)
{
return dd[u]+dd[v]-2*dd[LCA(u,v)];
}
bool isParent(ll x,ll y)
{
return in[x]<=in[y]&&out[y]<=out[x];
}
void Init(int N,int A[],int B[],int D[])
{
for(int i=0;i<N-1;i++)
{
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
dfs();
}
ll Query(int s,int x[],int t,int y[])
{
vector<ll> vv;
for(int i=0;i<s;i++) vv.pb(x[i]);
for(int i=0;i<t;i++) vv.pb(y[i]),vt[y[i]]=2;
sort(vv.begin(),vv.end(),cmp);
ll k=vv.size();
for(int i=1;i<k;i++)
{
ll v=LCA(vv[i],vv[i-1]);
vv.pb(v);
}
sort(vv.begin(),vv.end(),cmp);
stack<int>st;
for(int i=0;i<vv.size();i++)
{
if(cnt[vv[i]]==0)
{
while(!st.empty()&&(!isParent(st.top(),vv[i]))) st.pop();
if(!st.empty()) c[st.top()].pb({vv[i],dis(st.top(),vv[i])});
st.push(vv[i]);
cnt[vv[i]]=1;
}
}
//cout << '\n';
dfs1(vv[0],0);
dfs2(vv[0],0,0);
ll ans=inf;
for(int i=0;i<s;i++)
{
ans=min(ans,min(dp1[x[i]],dp2[x[i]]));
}
for(int i=0;i<vv.size();i++)
{
cnt[vv[i]]=0;
c[vv[i]].clear();
vt[vv[i]]=0;
}
return ans;
}
Compilation message
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:137:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i=0;i<vv.size();i++)
| ~^~~~~~~~~~
factories.cpp:155:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(int i=0;i<vv.size();i++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
94664 KB |
Output is correct |
| 2 |
Incorrect |
1262 ms |
104032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
94540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
94664 KB |
Output is correct |
| 2 |
Incorrect |
1262 ms |
104032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
