#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;
ll pre[500009],dep[500009],td[500009];
ll anc[500009][20],cnt = 0;
vector<ll> G[500009],d[500009];
vector<ll> G2[500009],d2[500009];
void DFS(ll u,ll p)
{
anc[u][0] = p;
cnt++;
pre[u] = cnt;
//cerr << u << "_" << td[u] << "_" << dep[u] << endl;
for(int i = 1;i < 20;i++)
{
anc[u][i] = anc[anc[u][i-1]][i-1];
}
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);
}
}
ll LCA(ll a,ll b)
{
if(a == 0 || b == 0) return 0LL;
if(td[a] < td[b]) swap(a,b);
int left = td[a] - td[b];
for(int i = 0;i < 20;i++)
{
if((left>>i) & 1) a = anc[a][i];
}
if(a == b) return a;
for(int i = 19;i >= 0;i--)
{
if(anc[a][i] != anc[b][i])
{
a = anc[a][i];
b = anc[b][i];
}
}
return anc[a][0];
}
const bool cmp(const ll &a,const ll & 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]);
}
DFS(1,0);
}
vector<ll> vs;
ll temp[500009];
ll stk[500009];
ll ans = 10000000000000000;
ll s,x[500009],t,y[500009];
void add_edge(ll a,ll 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);
}
ll dis[500009];
set<int> used;
void DKS()
{
priority_queue<pii,vector<pii>,greater<pii> > pq;
for(auto t : used)
{
dis[t] = 10000000000000000;
}
for(int i = 0;i < s;i++)
{
pq.push({0,x[i]});
}
while(!pq.empty())
{
ll u = pq.top().ss,t = pq.top().ff;
pq.pop();
if(t >= dis[u]) continue;
dis[u] = t;
for(int i = 0;i < G2[u].size();i++)
{
ll v = G2[u][i];
if(dis[v] < 10000000000000000) continue;
pq.push({dis[u] + d2[u][i],v});
}
}
for(int i = 0;i < t;i++)
{
assert(dis[y[i]] < 10000000000000000);
ans = min(ans,dis[y[i]]);
}
}
long long Query(int S, int X[], int T, int Y[]) {
vs.clear();
s = S;
used.clear();
for(int i = 0;i < S;i++)
{
X[i]++;
used.insert(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]++;
used.insert(Y[i]);
y[i] = Y[i];
G2[Y[i]].clear();
d2[Y[i]].clear();
vs.push_back(Y[i]);
if(temp[Y[i]] == 1) fg = 1;
}
for(int i = 0;i < S;i++) temp[X[i]] = 0;
if(fg == 1) 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]);
if(!used.count(p))
{
used.insert(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();
return ans;
}
Compilation message
factories.cpp: In function 'void DFS(long long int, long long int)':
factories.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i = 0;i < G[u].size();i++)
| ~~^~~~~~~~~~~~~
factories.cpp: In function 'void DKS()':
factories.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0;i < G2[u].size();i++)
| ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i = 0;i < vs.size();i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
47980 KB |
Output is correct |
| 2 |
Correct |
2097 ms |
57608 KB |
Output is correct |
| 3 |
Runtime error |
363 ms |
115180 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
98 ms |
96236 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
47980 KB |
Output is correct |
| 2 |
Correct |
2097 ms |
57608 KB |
Output is correct |
| 3 |
Runtime error |
363 ms |
115180 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
