#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll inf = 1e16 + 7;
vector<LL> g[N];
ll n,chainHead[N],curChain[N],posIn[N],now = 1,cnt = 1,child[N],dep[N],par[N];
ll suf[N],ans;
void DFS(ll u,ll p){
child[u] = 1; par[u] = p; //cout<<par[0]<<"x\n"; //exit(0);
//cout<<u<<" x "<<p<<"\n";
for (auto i : g[u]){
ll v = i.fs;
if (v != p) dep[v] = dep[u] + i.sc,DFS(v,u),child[u] += child[v];
}
}
void DFS_hld(ll u,ll p){
curChain[u] = now;
if (chainHead[now] == -1) chainHead[now] = u;
ll chosen = -1,mx = 0;
for (auto i : g[u]){
ll v = i.fs;
if (v != p&&child[v] > mx) mx = child[v],chosen = v;
}
if (chosen >= 0) DFS_hld(chosen,u);
for (auto i : g[u]){
ll v = i.fs;
if (v != p&&v != chosen) now++,DFS_hld(v,u);
}
}
void Init(int sz,int A[],int B[],int D[]){
memset(chainHead,-1,sizeof(chainHead));
for (ll i = 0;i < sz - 1;i++){
ll x = A[i],y = B[i],w = D[i];
g[x].push_back({y,w}); g[y].push_back({x,w});
}
DFS(0,-1); DFS_hld(0,-1);
}
struct Node{
ll path,Lnode,d,type;
};
vector<Node> v;
/// suffix min
void To_root(ll now,ll d,ll type){
while(now >= 0){
ll path = curChain[now],nxt = par[chainHead[path]];
//cout<<now<<" "<<par[3]; exit(0);
v.push_back({path,now,d,type}); now = nxt;
}
//exit(0);
}
bool lf1(Node a,Node b){
return a.path < b.path;
}
bool lf2(Node a,Node b){
return dep[a.Lnode] < dep[b.Lnode] || (dep[a.Lnode] == dep[b.Lnode] && a.type < b.type);
}
void calSuf(ll L,ll R){
vector<Node> have;
for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
suf[have.size()] = inf;
for (ll i = have.size() - 1;i >= 0;i--){
suf[i] = suf[i + 1];
if (have[i].type) suf[i] = min(suf[i],v[i].d);
}
for (ll i = have.size() - 1;i >= 0;i--){
if (have[i].type) continue;
ans = min(ans,have[i].d + suf[i + 1] - 2*dep[have[i].Lnode]);
}
}
ll Query(int S,int X[],int T,int Y[]){
v.clear(); ans = inf;
for (ll i = 0;i < S;i++) To_root(X[i],dep[X[i]],0);
for (ll i = 0;i < T;i++) To_root(Y[i],dep[Y[i]],1);
sort(v.begin(),v.end(),lf1); ll sz = v.size(); suf[sz] = inf;
//for (auto i : v) cout<<i.path<<" "<<i.Lnode<<" "<<i.d<<" "<<i.type<<"\n"; cout<<"\n";
//exit(0);
for (ll i = 0;i < sz;i){
if (v[i].type){
i++; continue;
}
ll j = i + 1;
while(j < sz&&v[j].path == v[i].path) j++;
calSuf(i,j - 1); i = j;
//cout<<v[i].d<<" "<<suf[i + 1]<<" "<<dep[v[i].Lnode]<<"\n";
}
return ans;
}
Compilation message
factories.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
factories.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
factories.cpp: In function 'void calSuf(long long int, long long int)':
factories.cpp:76:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
76 | for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
| ^~~
factories.cpp:76:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
76 | for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
| ^~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:95:26: warning: for increment expression has no effect [-Wunused-value]
95 | for (ll i = 0;i < sz;i){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
16552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
16156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
16552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
