#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=5e4+54;
const ll mod =1e9+7 ;
const ll base=1e18;
vector<pll> adj[maxn];
ll dep[maxn];
ll dep1[maxn];
ll anc[maxn][20];
ll col[maxn];
vector<ll> adj1[maxn];
ll f[maxn];
ll l[maxn];
ll cnt=0;
void dfs(ll u,ll par)
{
cnt++;
f[u]=cnt;
anc[u][0]=par;
for (int i=1;i<19;i++)
{
anc[u][i]=anc[anc[u][i-1]][i-1];
}
for (auto to:adj[u])
{
if (to.ff==par) continue;
dep[to.ff]=dep[u]+1;
dep1[to.ff]=dep[u]+to.ss;
dfs(to.ff,u);
}
l[u]=cnt;
}
ll lca(ll x,ll y)
{
if (dep[x]< dep[y]) swap(x,y);
ll kc= dep[x]-dep[y];
for (int i=18;i>=0;i--)
{
if (kc&(1ll<<i))
{
x=anc[x][i];
}
}
if (x==y) return x;
for (int i=18;i>=0;i--)
{
if (anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][0];
}
ll kc(ll x,ll y)
{
return dep1[x]+dep1[y]-2*(dep1[lca(x,y)]);
}
ll dp1[maxn];
ll dp2[maxn];
ll ans=1e18;
void dfs1(ll u)
{
dp1[u]=dp2[u]=1e15;
if (col[u]==1) dp1[u]=0;
else if (col[u]==2) dp2[u]=0;
for (auto to:adj1[u])
{
dfs1(to);
dp1[u]=min(dp1[u],dp1[to]+kc(to,u));
dp2[u]=min(dp2[u],dp2[to]+kc(to,u));
}
ans=min(ans,dp1[u]+dp2[u]);
}
void Init(int N,int A[],int B[],int D[])
{
ll n= N;
for (int i=0;i<n-1;i++)
{
A[i]++;
B[i]++;
adj[A[i]].pb(make_pair(B[i],D[i]));
adj[B[i]].pb(make_pair(A[i],D[i]));
}
dfs(1,0);
}
long long Query(int S,int X[],int T,int Y[])
{
ans=1e18;
vector<pll> vt;
for (int i=0;i<S;i++)
{
X[i]++;
col[X[i]]=1;
vt.pb(make_pair(f[X[i]],X[i]));
}
for (int i=0;i<T;i++)
{
Y[i]++;
col[Y[i]]=2;
vt.pb(make_pair(f[Y[i]],Y[i]));
}
sort(vt.begin(),vt.end());
vector<pll> nw;
for (int i=1;i<vt.size();i++)
{
ll h=lca(vt[i].ss,vt[i-1].ss);
nw.pb(make_pair(f[h],h));
}
for (auto p:vt)
{
nw.pb(p);
}
nw.pb(make_pair(f[1],1));
sort(nw.begin(),nw.end());
nw.resize(unique(nw.begin(),nw.end())-nw.begin());
stack<ll> st;
for (auto p:nw)
{
while (st.size()&&l[st.top()]<p.ff) st.pop();
if (st.size())
{
adj1[st.top()].pb(p.ss);
}
st.push(p.ss);
}
dfs1(1);
for (auto p:nw)
{
col[p.ss]=0;
adj1[p.ss].clear();
}
cout <<ans<<endl;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.txt", "r"))
{
freopen("test.txt", "r", stdin);
// freopen("team.out", "w", stdout);
}
}*/
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i=1;i<vt.size();i++)
| ~^~~~~~~~~~
factories.cpp:150:1: warning: no return statement in function returning non-void [-Wreturn-type]
150 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
6252 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
5868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
6252 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
