#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;
int pre[500009],td[500009],fst[500009];
ll dep[500009],inv[500009];
int st[21][1500009],cnt = 0;
vector<int> G[500009],d[500009];
vector<int> G2[500009];
vector<ll> d2[500009];
vector<int> ov;
void DFS(int u,int p)
{
cnt++;
pre[u] = cnt;
inv[pre[u]] = u;
fst[u] = ov.size();
ov.push_back(pre[u]);
for(int i = 0;i < G[u].size();i++)
{
int v = G[u][i];
if(v == p) continue;
dep[v] = dep[u] + d[u][i];
td[v] = td[u] + 1;
DFS(v,u);
ov.push_back(pre[u]);
}
}
int LCA(int a,int b)
{
if(a == b) return a;
if(a == 0 || b == 0) return 0LL;
if(fst[a] > fst[b]) swap(a,b);
int ret;
int tp = __lg(fst[b]-fst[a]);
//cout << fst[a] << " " << fst[b] << " " << tp << " " << min(st[tp][fst[a]],st[tp][fst[b] - (1<<tp)]) << endl;
return inv[min(st[tp][fst[a]],st[tp][fst[b] - (1<<tp)])];
// ret = min()
}
const bool cmp(const int &a,const int & b)
{
return pre[a] < pre[b];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0;i < N-1;i++)
{
A[i]++;
B[i]++;
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
d[A[i]].push_back(D[i]);
d[B[i]].push_back(D[i]);
}
td[1] = 1;
ov.push_back(0);
DFS(1,0);
for(int i = 0;i < ov.size();i++)
{
st[0][i] = ov[i];
}
for(int i = 1;i < 21;i++)
{
for(int j = 0;j+(1<<(i-1)) < ov.size();j++)
{
st[i][j] = min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
//cout << st[i][j] << " ";
}
//cout << endl;
}
}
vector<ll> vs;
int temp[500009];
int stk[500009];
ll ans = 10000000000000000;
int s,x[500009],t,y[500009];
void add_edge(int a,int b)
{
ll tp = abs(dep[a]-dep[b]);
//cerr << a << "_" << b << "_" << tp << endl;
G2[a].push_back(b);
G2[b].push_back(a);
d2[a].push_back(tp);
d2[b].push_back(tp);
}
bool iss[500009],ist[500009];
ll dp1[500009],dp2[500009];
bool used[500009];
vector<ll> us;
void DFS2(int u,int p)
{
if(iss[u]) dp1[u] = 0;
if(ist[u]) dp2[u] = 0;
for(int i = 0;i < G2[u].size();i++)
{
int v = G2[u][i];
if(v == p) continue;
DFS2(v,u);
dp1[u] = min(dp1[v]+d2[u][i],dp1[u]);
dp2[u] = min(dp2[v]+d2[u][i],dp2[u]);
}
//cout << u << "_" << dp1[u] << "_" << dp2[u] << endl;
ans = min(ans,dp1[u] + dp2[u]);
}
void DKS()
{
int i;
for(i = 0;i < s;i++)
{
iss[x[i]] = 1;
}
for(i = 0;i < t;i++)
{
ist[y[i]] = 1;
}
for(auto tt : us)
{
assert(tt >= 0 && tt <= 500000);
dp1[tt] = dp2[tt] = 10000000000000000;
}
DFS2(x[0],0);
for(i = 0;i < s;i++)
{
iss[x[i]] = 0;
}
for(i = 0;i < t;i++)
{
ist[y[i]] = 0;
}
}
long long Query(int S, int X[], int T, int Y[]) {
vs.clear();
s = S;
us.clear();
for(int i = 0;i < S;i++)
{
X[i]++;
used[X[i]] = 1;
us.push_back(X[i]);
x[i] = X[i];
G2[X[i]].clear();
d2[X[i]].clear();
temp[X[i]] = 1;
vs.push_back(X[i]);
}
int fg = 0;
t = T;
for(int i = 0;i < T;i++)
{
Y[i]++;
y[i] = Y[i];
G2[Y[i]].clear();
d2[Y[i]].clear();
vs.push_back(Y[i]);
if(used[Y[i]] == 0)us.push_back(Y[i]);
used[Y[i]] = 1;
if(temp[Y[i]] == 1) fg = 1;
}
for(int i = 0;i < S;i++)
{
temp[X[i]] = 0;
}
if(fg == 1)
{
for(int i = 0;i < S;i++) used[X[i]] = 0;
for(int i = 0;i < T;i++) used[Y[i]] = 0;
return 0;
}
sort(vs.begin(),vs.end(),cmp);
stk[0] = 0;
int sz = 1;
ans = 10000000000000000;
for(int i = 0;i < vs.size();i++)
{
ll u = vs[i];
ll p = LCA(u,stk[sz-1]);
//cerr << vs[i] << " p = " << p << endl;
if(used[p] == 0)
{
used[p] = 1;
us.push_back(p);
G2[p].clear();
d2[p].clear();
}
if(p == stk[sz-1]) stk[sz++] = u;
else
{
while(sz > 1 && td[stk[sz-2]] >= td[p])
{
add_edge(stk[sz-1],stk[sz-2]);
sz--;
}
if(stk[sz-1] != p)
{
add_edge(stk[sz-1],p);
stk[sz-1] = p;
}
stk[sz++] = u;
}
}
for (int i = 1; i < sz - 1; ++i) add_edge(stk[i], stk[i + 1]);
DKS();
for(int i = 0;i < S;i++) used[X[i]] = 0;
for(int i = 0;i < T;i++) used[Y[i]] = 0;
return ans;
}
Compilation message
factories.cpp: In function 'void DFS(int, int)':
factories.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i = 0;i < G[u].size();i++)
| ~~^~~~~~~~~~~~~
factories.cpp: In function 'int LCA(int, int)':
factories.cpp:37:9: warning: unused variable 'ret' [-Wunused-variable]
37 | int ret;
| ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0;i < ov.size();i++)
| ~~^~~~~~~~~~~
factories.cpp:66:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int j = 0;j+(1<<(i-1)) < ov.size();j++)
| ~~~~~~~~~~~~~^~~~~~~~~~~
factories.cpp: In function 'void DFS2(int, int)':
factories.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0;i < G2[u].size();i++)
| ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:177:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int i = 0;i < vs.size();i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
642 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2317 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
642 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
