#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
#define MAX_N 500000
#define MAX_Q 100000
#define MAX_SUM_ST 1000000
#define MAX_VALUE 1000000000
#define ff first
#define ss second
#define pb push_back
#include "factories.h"
#define mp make_pair
typedef long long ll;
using namespace std;
ll n,a[1000001],b[1000001],d[1000001],distnce[1000001],euler[5000000],k=0,first[1000001],belong[25][1000001],sz[1000001],centroid,nearest[1000001],o=0;
bool vis[1000001];
vector<int>vec;
pair<ll,ll>st[25][2000001];
vector<pair<ll,ll> >adj[1000001];
void dfs(ll node,ll par,ll dis){
distnce[node]=dis;
for(int i=0;i<adj[node].size();i++){
if(adj[node][i].ff!=par){
dfs(adj[node][i].ff,node,dis+adj[node][i].ss);
}
}
}
void build(ll node,ll par){
k++;
euler[k]=distnce[node];
first[node]=k;
for(int i=0;i<adj[node].size();i++){
if(adj[node][i].ff!=par){
build(adj[node][i].ff,node);
k++;
euler[k]=distnce[node];
}
}
}
void dfs1(ll node,ll par){
sz[node]=1;
for(int i=0;i<adj[node].size();i++){
if(adj[node][i].ff!=par && vis[adj[node][i].ff]==0){
dfs1(adj[node][i].ff,node);
sz[node]+=sz[adj[node][i].ff];
}
}
}
void dfs2(ll node,ll par,ll level){
belong[level][node]=centroid;
// cout << level << ' ' << node << ' ' << centroid << '\n';
for(int i=0;i<adj[node].size();i++){
if(adj[node][i].ff!=par && vis[adj[node][i].ff]==0){
dfs2(adj[node][i].ff,node,level);
}
}
}
void solve(ll node,ll par,ll level){
// cout << node << '\n';
o++;
dfs1(node,par);
ll cent=node;
while(1){
bool f=true;
for(int i=0;i<adj[cent].size();i++){
if(sz[adj[cent][i].ff]<sz[cent] && vis[adj[cent][i].ff]==0 && sz[adj[cent][i].ff]*2>sz[node]){
f=false;
cent=adj[cent][i].ff;
break;
}
}
if(f) break;
}
centroid=cent;
// cout << cent << ' ' << level << '\n';
dfs2(cent,-1,level);
vis[cent]=1;
for(int i=0;i<adj[cent].size();i++){
if(vis[adj[cent][i].ff]==0){
solve(adj[cent][i].ff,-1,level+1);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n=(ll)N;
for(int i=0;i<(N-1);i++){
a[i]=(ll)A[i];
b[i]=(ll)B[i];
d[i]=(ll)D[i];
adj[a[i]].pb(mp(b[i],d[i]));
adj[b[i]].pb(mp(a[i],d[i]));
}
dfs(0,-1,0);
build(0,-1);
for(int i=1;i<=k;i++){
st[0][i]={euler[i],i};
}
int l=log2(k);
for(int i=1;i<=l;i++){
for(int j=1;j<=(k-(1<<i)+1);j++){
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
solve(0,-1,1);
for(int i=1;i<=n;i++){
nearest[i]=1e18;
}
}
ll dist(int x,int y){
int xx=min(first[x],first[y]);
int yy=max(first[x],first[y]);
// cout << xx << ' ' << yy << '\n';
int z=log2(yy-xx+1);
ll mn=(min(st[z][xx],st[z][yy-(1<<z)+1])).ff;
return distnce[x]+distnce[y]-2*mn;
}
void add(int node,int level){
int cent=belong[level][node];
// cout << node << ' ' << level << ' ' << cent << '\n';
nearest[cent]=min(nearest[cent],dist(node,cent));
vec.pb(cent);
if(node!=cent) add(node,level+1);
}
ll query(int node,int level){
int cent=belong[level][node];
if(cent==node) return nearest[cent];
return min(nearest[cent]+dist(node,cent),query(node,level+1));
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;i++){
add(X[i],1);
}
ll ans=2e18;
for(int i=0;i<T;i++){
ans=min(ans,query(Y[i],1));
}
for(int i=0;i<vec.size();i++){
nearest[vec[i]]=1e18;
}
vec.clear();
return ans;
}
Compilation message
factories.cpp: In function 'void dfs(ll, ll, ll)':
factories.cpp:22:16: 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]
22 | for(int i=0;i<adj[node].size();i++){
| ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void build(ll, ll)':
factories.cpp:32:16: 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]
32 | for(int i=0;i<adj[node].size();i++){
| ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs1(ll, ll)':
factories.cpp:42:16: 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]
42 | for(int i=0;i<adj[node].size();i++){
| ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(ll, ll, ll)':
factories.cpp:52:16: 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]
52 | for(int i=0;i<adj[node].size();i++){
| ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void solve(ll, ll, ll)':
factories.cpp:65: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]
65 | for(int i=0;i<adj[cent].size();i++){
| ~^~~~~~~~~~~~~~~~~
factories.cpp:78:16: 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]
78 | for(int i=0;i<adj[cent].size();i++){
| ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:137:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i=0;i<vec.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
24812 KB |
Output is correct |
| 2 |
Correct |
998 ms |
44652 KB |
Output is correct |
| 3 |
Correct |
1344 ms |
44656 KB |
Output is correct |
| 4 |
Correct |
1389 ms |
45036 KB |
Output is correct |
| 5 |
Correct |
1578 ms |
45292 KB |
Output is correct |
| 6 |
Incorrect |
441 ms |
44140 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
24428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
24812 KB |
Output is correct |
| 2 |
Correct |
998 ms |
44652 KB |
Output is correct |
| 3 |
Correct |
1344 ms |
44656 KB |
Output is correct |
| 4 |
Correct |
1389 ms |
45036 KB |
Output is correct |
| 5 |
Correct |
1578 ms |
45292 KB |
Output is correct |
| 6 |
Incorrect |
441 ms |
44140 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
