///breaker
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=5e5+7;
const int inf=1e18+7;
vector<ii>adj[maxn];
int sz[maxn];
bool used[maxn];
int p[25][maxn];
ll up[25][maxn];
ll minn[maxn];
int h[maxn];
vector<int>ancestors[maxn];
int dfs(int u,int par)
{
sz[u]=1;
for(ii pp:adj[u]){
int v=pp.fi;
int w=pp.se;
if(v==par||used[v])continue;
sz[u]+=dfs(v,u);
}
return sz[u];
}
void dfs1(int u,int par)
{
for(ii pp:adj[u]){
int v=pp.fi;
int w=pp.se;
if(v==par)continue;
p[0][v]=u;
up[0][v]=w;
h[v]=h[u]+1;
dfs1(v,u);
}
}
void dfs2(int u,int par,int cen)
{
ancestors[u].push_back(cen);
for(ii pp:adj[u]){
int v=pp.fi;
int w=pp.se;
if(v==par||used[v])continue;
dfs2(v,u,cen);
}
}
int getcen(int u,int par,int treesize)
{
for(ii pp:adj[u]){
int v=pp.fi;
int w=pp.se;
if(v==par||used[v])continue;
if((sz[v]<<1)>treesize)return getcen(v,u,treesize);
}
return u;
}
void buildcen(int u,int par)
{
int C=getcen(u,0,dfs(u,0));
used[C]=1;
dfs2(C,0,C);
for(ii pp:adj[u]){
int v=pp.fi;
int w=pp.se;
if(v==par||used[v])continue;
buildcen(v,u);
}
}
ll path(int u,int v)
{
if(h[u]<h[v])swap(u,v);
int del=h[u]-h[v];
ll ans=0;
for(int i=20;i>=0;i--)if(bit(del,i)){
ans+=up[i][u];
u=p[i][u];
}
if(u==v)return ans;
for(int i=20;i>=0;i--)if(p[i][u]!=p[i][v]){
ans+=up[i][u];
ans+=up[i][v];
u=p[i][u];
v=p[i][v];
}
ans+=up[0][u];
ans+=up[0][v];
return ans;
}
void Init(int N,int A[],int B[],int D[])
{
for(int i=0;i<N-1;i++){
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
dfs1(0,0);
for(int i=1;i<=20;i++){
for(int j=0;j<N;j++){
p[i][j]=p[i-1][p[i-1][j]];
up[i][j]=up[i-1][j]+up[i-1][p[i-1][j]];
}
}
buildcen(0,0);
for(int i=0;i<N;i++){
minn[i]=inf;
}
}
long long Query(int S, int X[], int T, int Y[])
{
vector<int>tmp;
for(int i=0;i<S;i++){
tmp.push_back(X[i]);
for(int y:ancestors[X[i]]){
minn[y]=min(minn[y],path(X[i],y));
}
}
ll ans=inf;
for(int i=0;i<T;i++){
for(int y:ancestors[Y[i]]){
ans=min(ans,minn[y]+path(Y[i],y));
}
}
for(int x:tmp){
for(int y:ancestors[x]){
minn[y]=inf;
}
}
return ans;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message
factories.cpp:16:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
16 | const int inf=1e18+7;
| ~~~~^~
factories.cpp: In function 'int dfs(int, int)':
factories.cpp:30:13: warning: unused variable 'w' [-Wunused-variable]
30 | int w=pp.se;
| ^
factories.cpp: In function 'void dfs2(int, int, int)':
factories.cpp:53:13: warning: unused variable 'w' [-Wunused-variable]
53 | int w=pp.se;
| ^
factories.cpp: In function 'int getcen(int, int, int)':
factories.cpp:62:13: warning: unused variable 'w' [-Wunused-variable]
62 | int w=pp.se;
| ^
factories.cpp: In function 'void buildcen(int, int)':
factories.cpp:75:13: warning: unused variable 'w' [-Wunused-variable]
75 | int w=pp.se;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
129872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
129872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
129872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
