#include "factories.h"
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
vector<vp> adj;
int n;
vp ed;
vp table;
vp seg;
vi cost;
vi order;
void dfs(int x,int p,int h,int w) {
cost[x] = w;
ed.push_back({x,h});;
table[x] = {ed.size(),0};
for (auto v : adj[x]) {
if (v.first==p) continue;
dfs(v.first,x,h+1,w+v.second);
ed.push_back({x,h});
}
order[x] = ed.size()-1;
table[x].second = ed.size();
}
//int min(int a,int b) return a<b?a:b;
int lca(int u,int v) {
int l = min(min(table[u].first,table[u].second),min(table[v].first,table[v].second))-1;
int r = max(max(table[u].first,table[u].second),max(table[v].first,table[v].second))-1;
l+=ed.size();
r+=ed.size()+1;
pri ans = {1e9,1e9};
for (;l<r;l/=2,r/=2) {
if (l&1) ans=min(seg[l++],ans);
if (r&1) ans=min(seg[--r],ans);
}
return ans.second;
}
void Init(int N, int A[],int B[],int D[]) {
n = N;
adj = vector<vp>(n);
table = vp(n);
cost = vi(n);
order = vi(n);
for (int i = 0;i<n;i++) {
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
dfs(0,-1,0,0);
seg = vp(2*ed.size()+1);
int m = ed.size();
for (int i = 0;i<m;i++) seg[i+m] = {ed[i].second,ed[i].first};
for (int i = m-1;i>0;i--) {
seg[i] = min(seg[2*i],seg[2*i+1]);
}
}
ll Query(int S,int X[],int T, int Y[]) {
ll ANS = 1e18;
priority_queue<array<ll,3>> pq;
for (int i = 0;i<S;i++) {
pq.push(array<ll,3>{-order[X[i]],cost[X[i]],(int)1e18});
}
for (int i = 0;i<T;i++) {
pq.push(array<ll,3>{-order[Y[i]],(int)1e18,cost[Y[i]]});
}
while (pq.size()>1) {
auto a = pq.top();
pq.pop();
auto b = pq.top();
pq.pop();
//cout<<ed[-a[0]].first<<" "<<ed[-b[0]].first<<" "<<lca(ed[-a[0]].first,ed[-b[0]].first)<<" "<<a[1]<<" "<<a[2]<<" "<<b[1]<<" "<<b[2]<<endl;
int lc = lca(ed[-a[0]].first,ed[-b[0]].first);
ll lch = cost[lc];
ANS = min(ANS,min( - 2*lch + a[1] + b[2] , a[2]+b[1] - 2*lch));
pq.push({-order[lc],min(a[1],b[1]),min(a[2],b[2])});
}
return ANS;
}
/*int32_t main() {
Init(7,new int[6]{0,1,2,2,4,1},new int[6]{1,2,3,4,5,6},new int[6]{4,4,5,6,5,3});
Query(1,new int[1]{2},1,new int[1]{5});
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
