#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 maincent,n,a[1000001],b[1000001],d[1000001],k=0,first[1000001],belong[25][1000001],sz[1000001],centroid,nearest[1000001],o=0,p[1000001];
bool vis[1000001];
vector<ll>child[1000001];
vector<ll>pre[1000001];
vector<int>vec;
vector<pair<ll,ll> >adj[1000001];
ll cnt[1000001],K=0,rr[1000001];
void dfs(int node,int par){
K++;
cnt[node]=K;
for(int i=0;i<child[node].size();i++){
dfs(child[node][i],node);
}
rr[node]=K;
}
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 dfs3(ll node,ll par,ll dis,ll cent){
// cout << cnt[node] << ' ' << cnt[cent] << '\n';
pre[cent][cnt[node]-cnt[cent]]=dis;
for(int i=0;i<adj[node].size();i++){
if(adj[node][i].ff!=par && vis[adj[node][i].ff]==0){
dfs3(adj[node][i].ff,node,dis+adj[node][i].ss,cent);
}
}
}
void dfs2(ll node){
pre[node].resize(rr[node]-cnt[node]+1);
dfs3(node,-1,0,node);
vis[node]=1;
for(int i=0;i<child[node].size();i++){
dfs2(child[node][i]);
}
}
void solve(ll node,ll par,ll level,ll parent){
// 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;
}
if(level==1) maincent=cent;
centroid=cent;
// cout << cent << ' ' << level << '\n';
p[cent]=parent;
child[parent].pb(cent);
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,cent);
}
}
}
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]));
}
solve(0,-1,1,-1);
for(int i=0;i<n;i++){
nearest[i]=1e18;
}
dfs(maincent,-1);
memset(vis,0,sizeof(vis));
dfs2(maincent);
}
void add(int node,int cent){
if(cent==-1) return;
nearest[cent]=min(nearest[cent],pre[cent][cnt[node]-cnt[cent]]);
// cout << node << ' ' << cent << ' ' << nearest[cent] << '\n';
vec.pb(cent);
add(node,p[cent]);
}
ll query(int node,int cent){
if(cent==-1) return 2e18;
return min(nearest[cent]+pre[cent][cnt[node]-cnt[cent]],query(node,p[cent]));
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;i++){
add(X[i],X[i]);
}
ll ans=2e18;
for(int i=0;i<T;i++){
ans=min(ans,query(Y[i],Y[i]));
}
for(int i=0;i<vec.size();i++){
nearest[vec[i]]=1e18;
}
vec.clear();
return ans;
}
Compilation message
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<child[node].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs1(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 dfs3(ll, ll, 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)':
factories.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0;i<child[node].size();i++){
| ~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void solve(ll, ll, ll, ll)':
factories.cpp:63: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]
63 | 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:120:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i=0;i<vec.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
72172 KB |
Output is correct |
| 2 |
Correct |
492 ms |
82156 KB |
Output is correct |
| 3 |
Correct |
572 ms |
82156 KB |
Output is correct |
| 4 |
Correct |
563 ms |
82540 KB |
Output is correct |
| 5 |
Correct |
636 ms |
82796 KB |
Output is correct |
| 6 |
Correct |
333 ms |
81792 KB |
Output is correct |
| 7 |
Correct |
572 ms |
82156 KB |
Output is correct |
| 8 |
Correct |
573 ms |
82284 KB |
Output is correct |
| 9 |
Correct |
632 ms |
82668 KB |
Output is correct |
| 10 |
Correct |
338 ms |
81900 KB |
Output is correct |
| 11 |
Correct |
574 ms |
82284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
72044 KB |
Output is correct |
| 2 |
Correct |
3664 ms |
201428 KB |
Output is correct |
| 3 |
Correct |
5205 ms |
224604 KB |
Output is correct |
| 4 |
Correct |
1287 ms |
164168 KB |
Output is correct |
| 5 |
Correct |
6356 ms |
256128 KB |
Output is correct |
| 6 |
Correct |
5383 ms |
226528 KB |
Output is correct |
| 7 |
Correct |
2364 ms |
109548 KB |
Output is correct |
| 8 |
Correct |
709 ms |
99932 KB |
Output is correct |
| 9 |
Correct |
2734 ms |
115652 KB |
Output is correct |
| 10 |
Correct |
2381 ms |
110700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
72172 KB |
Output is correct |
| 2 |
Correct |
492 ms |
82156 KB |
Output is correct |
| 3 |
Correct |
572 ms |
82156 KB |
Output is correct |
| 4 |
Correct |
563 ms |
82540 KB |
Output is correct |
| 5 |
Correct |
636 ms |
82796 KB |
Output is correct |
| 6 |
Correct |
333 ms |
81792 KB |
Output is correct |
| 7 |
Correct |
572 ms |
82156 KB |
Output is correct |
| 8 |
Correct |
573 ms |
82284 KB |
Output is correct |
| 9 |
Correct |
632 ms |
82668 KB |
Output is correct |
| 10 |
Correct |
338 ms |
81900 KB |
Output is correct |
| 11 |
Correct |
574 ms |
82284 KB |
Output is correct |
| 12 |
Correct |
50 ms |
72044 KB |
Output is correct |
| 13 |
Correct |
3664 ms |
201428 KB |
Output is correct |
| 14 |
Correct |
5205 ms |
224604 KB |
Output is correct |
| 15 |
Correct |
1287 ms |
164168 KB |
Output is correct |
| 16 |
Correct |
6356 ms |
256128 KB |
Output is correct |
| 17 |
Correct |
5383 ms |
226528 KB |
Output is correct |
| 18 |
Correct |
2364 ms |
109548 KB |
Output is correct |
| 19 |
Correct |
709 ms |
99932 KB |
Output is correct |
| 20 |
Correct |
2734 ms |
115652 KB |
Output is correct |
| 21 |
Correct |
2381 ms |
110700 KB |
Output is correct |
| 22 |
Correct |
4582 ms |
204000 KB |
Output is correct |
| 23 |
Correct |
4724 ms |
209704 KB |
Output is correct |
| 24 |
Correct |
6763 ms |
230368 KB |
Output is correct |
| 25 |
Correct |
6838 ms |
233436 KB |
Output is correct |
| 26 |
Correct |
6850 ms |
227052 KB |
Output is correct |
| 27 |
Execution timed out |
8037 ms |
257236 KB |
Time limit exceeded |
| 28 |
Halted |
0 ms |
0 KB |
- |
