#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define bk back()
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define For(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define Rof(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define nl '\n'
const int MOD = 1e9+7;
const ll INF = 1e18;
const int MX = 3e5+5;
const ld PI = acos((ld)-1);
mt19937 rng; // or mt19937_64
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
template<int SZ> struct Centroid{
vpi adj[SZ];
int lev[SZ], sub[SZ], par[SZ];
ll dist[32][SZ], stor[SZ], anc[32][SZ];//todo anc
bool done[SZ];
vpi cur;
void ae(int a, int b, int c){
adj[a].pb(mp(b,c));
adj[b].pb(mp(a,c));
}
void dfs(int x, int p){
sub[x]=1;
// int mx=0;
trav(y,adj[x])if(y.f!=p && !done[y.f]){
par[y.f]=x;
dbg(x,y.f);
dfs(y.f,x);
sub[x]+=sub[y.f];
// mx=max(mx,sub[y.f]);
}
// cur.pb(mp(mx,x));
}
int getCen(int x){
// cur.clear();
// dfs(x,x);
// trav(y,cur){
// dbg(x,y.f,y.s);
// if(max(y.f,sub[x]-y.f)*2<=sub[x])
// return y.s;
// }
// assert(false);
dfs(x,x);
int sz = sub[x];
while (1) {
pi mx = {0,0};
for (pi i: adj[x]) if (!done[i.f] && i.f != par[x]) mx = max(mx,{sub[i.f],i.f});
if (mx.f*2 > sz) x = mx.s;
else return x;
}
}
void genDist(int n, int par,int lev, ll d, int dad){
dist[lev][n]=d;
anc[lev][n]=dad;
trav(x,adj[n])if(x.f!=par){
genDist(x.f,n,lev,d+x.s,dad);
}
}
void gen(int CEN, int x){//CEN is prev cen
x=getCen(x);done[x]=1;
dbg(x);
lev[x]=(CEN==-1?0:lev[CEN]+1);
genDist(x,x,lev[x],0,x);
trav(y,adj[x])if(!done[y.f])gen(x,y.f);
}
void init(int N){
For(i,N)done[i]=false;
For(i,N)stor[i]=INF;
gen(-1,0);
}
void upd(int n, int t=1){
For(i,lev[n]){
if(t==1)ckmin(stor[anc[i][n]],dist[i][n]);
else stor[anc[i][n]]=INF;
}
}
ll query(int n){
ll mn=INF;
For(i,lev[n]){
ckmin(mn, dist[i][n]+stor[anc[i][n]]);
}
return mn;
}
};
Centroid<MX> C;
void Init(int N, int A[], int B[], int D[]){
For(i,N-1){
C.ae(A[i],B[i],D[i]);
}
C.init(N);
}
ll Query(int S, int X[], int T, int Y[]){
ll mn=INF;
For(i,S)C.upd(X[i]);
For(i,T)ckmin(mn,C.query(Y[i]));
For(i,S)C.upd(X[i],-1);
return mn;
}
// int main(){
// int n,q;cin>> n>>q;
// int a[n],b[n],d[n];
// For(i,n-1){
// cin>>a[i];
// cin>>b[i];
// cin>>d[i];
// }
// dbg("HI");
// Init(n,a,b,d);
// }
Compilation message
factories.cpp: In instantiation of 'void Centroid<SZ>::gen(int, int) [with int SZ = 300005]':
factories.cpp:107:3: required from 'void Centroid<SZ>::init(int) [with int SZ = 300005]'
factories.cpp:130:10: required from here
factories.cpp:44:18: warning: statement has no effect [-Wunused-value]
44 | #define dbg(...) 0
| ^
factories.cpp:97:3: note: in expansion of macro 'dbg'
97 | dbg(x);
| ^~~
factories.cpp: In instantiation of 'void Centroid<SZ>::dfs(int, int) [with int SZ = 300005]':
factories.cpp:79:3: required from 'int Centroid<SZ>::getCen(int) [with int SZ = 300005]'
factories.cpp:96:5: required from 'void Centroid<SZ>::gen(int, int) [with int SZ = 300005]'
factories.cpp:107:3: required from 'void Centroid<SZ>::init(int) [with int SZ = 300005]'
factories.cpp:130:10: required from here
factories.cpp:44:18: warning: statement has no effect [-Wunused-value]
44 | #define dbg(...) 0
| ^
factories.cpp:63:4: note: in expansion of macro 'dbg'
63 | dbg(x,y.f);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
8044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
8044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
