#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 fi first
#define se second
#define pb emplace_back
#define inf 1000000000000000
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
using namespace std;
long long n,q;
vector<pair<long long,long long>> ke[maxn];
long long minn[maxn];
bool is_remove[maxn];
long long sz[maxn];
vector<pair<long long,long long>> par[maxn];
long long x[maxn],y[maxn];
long long dfs_size(long long u,long long parent = -1)
{
sz[u] = 1;
for(auto [v,_] : ke[u])
{
if(v == parent or is_remove[v]) continue;
sz[u] += dfs_size(v,u);
}
return sz[u];
}
long long dfs_centroid(long long u,long long tree_size,long long parent = 0)
{
for(auto [v,_] : ke[u])
{
if(v == parent or is_remove[v]) continue;
if(2 * sz[v] > tree_size) return dfs_centroid(v,tree_size,u);
}
return u;
}
void dfs_dist(long long u,long long parent,long long centroid,long long cur_len)
{
for(auto [v,w] : ke[u])
{
if(v == parent or is_remove[v]) continue;
dfs_dist(v,u,centroid,cur_len + w);
}
par[u].pb(cur_len,centroid);
}
void build_centroid(long long u)
{
long long centroid = dfs_centroid(u,dfs_size(u));
is_remove[centroid] = 1;
// do sth
for(auto [v,w] : ke[centroid])
{
if(is_remove[v]) continue;
dfs_dist(v,centroid,centroid,w);
}
for(auto [v,w] : ke[centroid])
{
if(is_remove[v]) continue;
build_centroid(v);
}
}
void update(long long u)
{
minn[u] = 0;
for(auto [dist,centroid] : par[u])
{
minn[centroid] = min(minn[centroid],dist);
}
}
void del(long long u)
{
minn[u] = inf;
for(auto [_,centroid] : par[u])
{
minn[centroid] = inf;
}
}
long long get(long long u)
{
long long ans = minn[u];
for(auto [dist,centroid] : par[u])
{
ans = min(ans,dist + minn[centroid]);
}
return ans;
}
void Init(int N, int A[], int B[], int D[])
{
fo(i,0,N - 2)
{
ke[A[i]].pb(B[i],D[i]);
ke[B[i]].pb(A[i],D[i]);
}
build_centroid(0);
}
long long Query(int S, int X[], int T, int Y[])
{
fo(i,0,S - 1) update(X[i]);
long long res = 1e18;
fo(i,0,T - 1) res = min(res,get(Y[i]));
cout << res << "\n";
fo(i,0,S - 1) del(X[i]);
}
//main()
//{
// #define name "TASK"
// if(fopen(name".inp","r"))
// {
// freopen(name".inp","r",stdin);
// freopen(name".out","w",stdout);
// }
// ios_base::sync_with_stdio(false);cin.tie(NULL);
// cin >> n >> q;
// fo(i,0,n - 1) minn[i] = inf;
// fo(i,1,n - 1)
// {
// int u,v,w;
// cin >> u >> v >> w;
// ke[u].pb(v,w);
// ke[v].pb(u,w);
// }
// build_centroid(0);
// while(q--)
// {
// int s,t;
// cin >> s >> t;
// fo(i,1,s)
// {
// cin >> x[i];
// update(x[i]);
// }
// int res = inf;
// fo(i,1,t)
// {
// cin >> y[i];
// res = min(res,get(y[i]));
// }
// cout << res;en;
// fo(i,1,s) del(x[i]);
// }
//}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:106:1: warning: no return statement in function returning non-void [-Wreturn-type]
106 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
86 ms |
138004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
137952 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
86 ms |
138004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
