#include "factories.h"
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
const int N = 500005;
typedef long long ll;
int dp[N][20],depth[N],subtree[N],vis[N],parent[N];
ll dist[N],XX[N][20],PP[N][20];
int A[N];ll B[N];
vector<pair<int,int>> adj[N];
int logt[N];
int QUERY=0;
void dfs1(int v, int p, int dep, ll x) {
dp[v][0]=p;
depth[v]=dep;
dist[v]=x;
for(int i=1;i<=logt[dep];i++) dp[v][i]=dp[dp[v][i-1]][i-1];
int c;
for(auto e:adj[v]) {
c=e.first;
if(c==p) continue;
dfs1(c,v,dep+1,x+e.second);
}
}
int find_centroid(int v, int p, int x) {
int c;
for(auto e:adj[v]) {
c=e.first;
if(c==p || vis[c] || subtree[c]<=x) continue;
return find_centroid(c,v,x);
}
return v;
}
void dfs2(int v, int p) {
int c;
subtree[v]=1;
for(auto e:adj[v]) {
c=e.first;
if(c==p || vis[c] ) continue;
dfs2(c,v);
subtree[v]+=subtree[c];
}
}
int lca(int a, int b) {
if(depth[a]>depth[b]) swap(a,b);
for(int i=logt[depth[b]];i>=0;i--) {
if(depth[b]-(1<<i)>=depth[a]) b=dp[b][i];
}
if(a==b) return a;
for(int i=logt[depth[b]];i>=0;i--) {
if(dp[a][i]!=dp[b][i]) a=dp[a][i],b=dp[b][i];
}
return dp[a][0];
}
ll distance(int a, int b) {
return dist[a]+dist[b]-2*dist[lca(a,b)];
}
void process(int v, int p) {
dfs2(v,0);
int u=find_centroid(v,0,subtree[v]/2);
vis[u]=1;
parent[u]=p;
int p2=u;
int i=0;
PP[u][i]=p2;
while(p2!=-1) {
XX[u][i]=distance(p2,u);
p2=parent[p2];i++;
PP[u][i]=p2;
}
int c;
for(auto e:adj[u]) {
c=e.first;
if(vis[c]) continue;
process(c,u);
}
}
void Init(int n, int A[], int B[], int D[]) {
for(int i=0;i<=n-2;i++) {
adj[A[i]+1].push_back({B[i]+1,D[i]});
adj[B[i]+1].push_back({A[i]+1,D[i]});
}
logt[0]=-1;
for(int i=1;i<=n;i++) {
logt[i]=logt[i-1];
if((i&-i)==i) logt[i]++;
}
dfs1(1,0,0,0);
process(1,-1);
}
long long Query(int S, int X[], int T, int Y[]) {
QUERY++;
int u,v;
for(int i=0;i<S;i++) {
u=X[i]+1;
for(int j=0;PP[u][j]!=-1;j++) {
v=PP[u][j];
assert(XX[u][j]==distance(u,v));
if(A[v]!=QUERY) {
A[v]=QUERY;B[v]=XX[u][j];
}
else if(B[v]>XX[u][j]) {
B[v]=XX[u][j];
}
}
}
ll ans=1e17;
for(int i=0;i<T;i++) {
u=Y[i]+1;
for(int j=0;PP[u][j]!=-1;j++) {
v=PP[u][j];
assert(XX[u][j]==distance(u,v));
if(A[v]==QUERY) {
// A[v]=QUERY;B[v]=X[u][j];
ans=min(XX[u][j]+B[v],ans);
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
250852 KB |
Output is correct |
2 |
Correct |
749 ms |
251116 KB |
Output is correct |
3 |
Correct |
1819 ms |
251116 KB |
Output is correct |
4 |
Correct |
1759 ms |
251116 KB |
Output is correct |
5 |
Correct |
2659 ms |
251136 KB |
Output is correct |
6 |
Correct |
336 ms |
251152 KB |
Output is correct |
7 |
Correct |
1856 ms |
251116 KB |
Output is correct |
8 |
Correct |
1886 ms |
251116 KB |
Output is correct |
9 |
Correct |
2549 ms |
251132 KB |
Output is correct |
10 |
Correct |
339 ms |
251152 KB |
Output is correct |
11 |
Correct |
1896 ms |
251116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
250852 KB |
Output is correct |
2 |
Correct |
3193 ms |
269596 KB |
Output is correct |
3 |
Execution timed out |
6000 ms |
272580 KB |
Execution timed out |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4359 ms |
269596 KB |
Output is correct |
2 |
Correct |
4416 ms |
269596 KB |
Output is correct |
3 |
Execution timed out |
6000 ms |
271600 KB |
Execution timed out |
4 |
Halted |
0 ms |
0 KB |
- |