#include "factories.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int NN=5e5+5;
const long long Inf=1e15;
int sz[NN],par[NN],fix[NN];
long long dist[NN][20],H[NN],mn[NN];
vector<pair<int,int> >V[NN];
void get_sz(int u,int p){
sz[u] = 1;
for(int i=0;i<V[u].size();i++){
if(V[u][i].f!=p && !fix[V[u][i].f]) get_sz(V[u][i].f,u),sz[u]+=sz[V[u][i].f];
}
}
int find_centroid(int u,int p,int Sz){
for(int i=0;i<V[u].size();i++){
if(V[u][i].f==p || fix[V[u][i].f]) continue;
if(sz[V[u][i].f] > Sz/2) return find_centroid(V[u][i].f,u,Sz);
}
return u;
}
void dfs(int u,int p,int h){
for(int i=0;i<V[u].size();i++){
if(V[u][i].f==p || fix[V[u][i].f]) continue;
dist[V[u][i].f][h] = dist[u][h] + V[u][i].s;
dfs(V[u][i].f,u,h);
}
}
void centroid_decomp(int u,int p,int h){
get_sz(u,0);
int c = find_centroid(u,0,sz[u]);
par[c] = p;
H[c] = h;
mn[c] =Inf;
dfs(c,0,h);
fix[c] = 1;
for(int i=0;i<V[c].size();i++){
if(!fix[V[c][i].f]) centroid_decomp(V[c][i].f,c,h+1);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N-1;i++){
V[A[i]].push_back({B[i],D[i]});
V[B[i]].push_back({A[i],D[i]});
}
centroid_decomp(1,0,0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> remove;
for(int i=0;i<S;i++){
int c = X[i];
while(c!=0){
if(mn[c] == Inf)remove.push_back(c);
mn[c] = min(mn[c],dist[X[i]][H[c]]);
c=par[c];
}
}
long long ans = Inf;
for(int i =0;i<T;i++){
int c = Y[i];
while(c!=0){
ans = min(mn[c] + dist[Y[i]][H[c]],ans);
c=par[c];
}
}
for(int i=0;i<remove.size();i++){
mn[remove[i]]=Inf;
}
return ans;
}
Compilation message
factories.cpp: In function 'void get_sz(int, int)':
factories.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i=0;i<V[u].size();i++){
| ~^~~~~~~~~~~~
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=0;i<V[u].size();i++){
| ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs(int, int, int)':
factories.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<V[u].size();i++){
| ~^~~~~~~~~~~~
factories.cpp: In function 'void centroid_decomp(int, int, int)':
factories.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<V[c].size();i++){
| ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<remove.size();i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12620 KB |
Output is correct |
| 2 |
Incorrect |
363 ms |
30832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
12236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12620 KB |
Output is correct |
| 2 |
Incorrect |
363 ms |
30832 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
