#include"factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
#include<assert.h>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
const int MAXN=5e5+100;
const int LOGN=21;
int up[MAXN][LOGN];
set<pair<int,int>> v[MAXN];
ll depth[MAXN];
int depth1[MAXN];
int par[MAXN];
int sub[MAXN];
bool visited[MAXN];
ll ans[MAXN];
void dfs(int node,int par){
depth1[node]=depth1[par]+1;
up[node][0]=par;
for(int i=1;i<LOGN;i++){
up[node][i]=up[up[node][i-1]][i-1];
}
for(auto x:v[node]){
if(x.F==par) continue;
depth[x.F]=depth[node]+x.S;
dfs(x.F,node);
}
}
int LCA(int a,int b){
if(depth1[a]<depth1[b]) swap(a,b);
ll d=depth1[a]-depth1[b];
for(ll i=LOGN-1;i>=0;i--){
if(d&(1<<i)) a=up[a][i];
}
if(a==b) return a;
for(ll i=LOGN-1;i>=0;i--){
if(up[a][i]==up[b][i]) continue;
a=up[a][i];
b=up[b][i];
}
return up[a][0];
}
ll dist(int a,int b){
return depth[a]+depth[b]-2*depth[LCA(a,b)];
}
int dfs1(int node,int par){
sub[node]=1;
for(auto x:v[node]) {
if(x.F==par) continue;
sub[node]+=dfs1(x.F,node);
}
return sub[node];
}
bool vis[MAXN];
int dfs2(int node, int p, int n) {
for (auto x: v[node]) {
if (x.F != p) {
if (!vis[x.F] && sub[x.F] > n / 2) {
return dfs2(x.F, node, n);
}
}
}
return node;
}
void build(int node = 0, int p = -1) {
dfs1(node,node);
int c = dfs2(node, -1, sub[node]);
vis[c] = true;
par[c] = p;
for (auto x: v[c]) {
if (!vis[x.F]) {
build(x.F, c);
}
}
}
void Init(int N, int A[], int B[], int D[]){
for(int i=0;i<N-1;i++){
v[A[i]].insert({B[i],D[i]});
v[B[i]].insert({A[i],D[i]});
}
dfs(0,0);
build(0,-1);
for(int i=0;i<=N;i++) ans[i]=1e18;
}
void clear(int x){
int node=x;
while(node!=-1){
ans[node]=1e18;
node=par[node];
}
}
// void update(int x){
// int node=x;
// while(node!=-1){
// ans[node]=min(ans[node],dist(x,node));
// node=par[node];
// }
// }
// ll query(int x){
// ll anss=1e18;
// int node=x;
// while(node!=-1){
// anss=min(anss,ans[node]+dist(x,node));
// node=par[node];
// }
// return anss;
// }
long long Query(int S, int X[], int T, int Y[]){
ll anss=1e18;
for(int i=0;i<T;i++){
int node=Y[i];
while(node!=-1){
ans[node]=min(ans[node],dist(Y[i],node));
node=par[node];
}
}
for(int i=0;i<S;i++) {
int node=X[i];
while(node!=-1){
anss=min(anss,ans[node]+dist(X[i],node));
node=par[node];
}
}
for(int i=0;i<T;i++){
int node=Y[i];
while(node!=-1){
if(ans[node]==1e18) break;
ans[node]=1e18;
node=par[node];
}
} return anss;
}
#ifdef IOI
int main(){
// Init(7, {0, 1, 2, 2, 4, 1}, {1, 2, 3, 4, 5, 6}, {4, 4, 5, 6, 5, 3});
// cout<<Query(2, 2, {0, 6}, {3, 4}); //returns 12.
// cout<<endl<<Query(3, 2, {0, 1, 3}, {4, 6}); //returns 3.
// cout<<endl<<Query(1, 1, {2}, {5}); //returns 11.
// return 0;
int N, Q;
assert(scanf("%i %i", &N, &Q) == 2);
int *A = (int*)malloc(sizeof(int) * (N - 1));
int *B = (int*)malloc(sizeof(int) * (N - 1));
int *D = (int*)malloc(sizeof(int) * (N - 1));
for(int a = 0; a < N - 1; a++){
assert(scanf("%i %i %i", A + a, B + a, D + a) == 3);
}
Init(N, A, B, D);
for(int a = 0; a < Q; a++){
int S, T;
assert(scanf("%i %i", &S, &T) == 2);
int *X = (int*)malloc(sizeof(int) * S);
int *Y = (int*)malloc(sizeof(int) * T);
for(int b = 0; b < S; b++){
assert(scanf("%i", X + b) == 1);
}
for(int b = 0; b < T; b++){
assert(scanf("%i", Y + b) == 1);
}
printf("%i\n", Query(S, X, T, Y));
free(X);
free(Y);
}
free(A);
free(B);
free(D);
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
49752 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
63840 KB |
Output is correct |
| 3 |
Execution timed out |
8052 ms |
63808 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
49756 KB |
Output is correct |
| 2 |
Execution timed out |
8063 ms |
161104 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
49752 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
63840 KB |
Output is correct |
| 3 |
Execution timed out |
8052 ms |
63808 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
