// REPUTATION RATING = -100
#include "factories.h"
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 5e5 + 5;
const ll oo = 1e16;
const int mod = 1e9 + 7;
int n, q, f[N][22], in[N], en[N], demin, a[N];
ll d[N], dp[N];
int st[N << 1];
vector<pii> p[N];
void dfs(int u,int v){
in[u] = ++demin;
a[in[u]] = u;
// cout << u << " ";
if(u == 1) for(int i = 0; i <= 20; i ++) f[u][i] = u;
else{
f[u][0] = v;
for(int i = 1; i <= 20; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
}
for(auto jj : p[u]){
int j = jj.fi;
int w = jj.se;
if(j == v) continue;
d[j] = d[u] + w;
dfs(j, u);
}
en[u] = demin;
}
bool kt(int u,int v){
return in[u] <= in[v] && in[v] <= en[u];
}
int lca(int u,int v){
if(kt(u, v)) return u;
else{
int kq = u;
for(int i = 20; i >= 0; i --){
if(kt(f[u][i], v)) kq = f[u][i];
else u = f[u][i];
}
return kq;
}
}
void update(int i,int x){
i += n - 1;
st[i] = x;
while(i > 1){
i /= 2;
if(d[st[i << 1]] < d[st[i << 1|1]]) st[i] = st[i << 1];
else st[i] = st[i << 1|1];
}
}
int get(int l,int r){
r++;
int ret = 0;
for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
if(l & 1){
if(d[st[l]] < d[ret]) ret = st[l];
l++;
}
if(r & 1){
--r;
if(d[st[r]] < d[ret]) ret = st[r];
}
}
return ret;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
d[0] = oo;
for(int i = 0; i < n - 1; i ++){
int x = A[i] + 1, y = B[i] + 1, w = D[i];
// cerr << x << " " << y << " " << w << "\n";
p[x].pb({y, w});
p[y].pb({x, w});
}
dfs(1, 0);
// cout << "\n";
for(int i = 1; i <= 2 * n; i ++) st[i] = 0;
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> vr;
for(int i = 0; i < S; i ++) vr.pb(++X[i]);
for(int i = 0; i < T; i ++) vr.pb(++Y[i]);
ll ans = (ll)1e18;
// ll kq = (ll)1e18;
// for(int i = 0; i < S; i ++)
// for(int j = 0; j < T; j ++)
// kq = min(kq, d[X[i]] + d[Y[j]] - 1LL * 2 * d[lca(X[i], Y[j])]);
// return kq;
// cerr << S << " " << T << "\n";
sort(vr.begin(), vr.end(), [] (int x,int y){return in[x] <= in[y];});
vector<int> R;
// for(auto j : vr) cerr << j << " ";
// cerr << "\n";
R.pb(vr[0]);
p[vr[0]].clear();
for(int i = 1; i < vr.size(); i ++){
int u = lca(vr[i], vr[i - 1]);
R.pb(vr[i]);
R.pb(u);
// cerr << vr[i] << " " << vr[i - 1] << " " << u << "d\n";
p[vr[i]].clear();
p[u].clear();
}
sort(all(R), [] (int x,int y){return x < y;});
R.resize(unique(all(R)) - R.begin());
sort(all(R), [] (int x,int y){return in[x] <= in[y];});
// for(auto j : R) cerr << j << " ";
// cerr << "\n";
stack<int> s;
s.push(R[0]);
dp[R[0]] = oo;
for(int i = 1; i < R.size(); i ++){
dp[R[i]] = oo;
while(!s.empty() && !kt(s.top(), R[i])) s.pop();
int w = d[R[i]] - d[s.top()];
// cerr << R[i] << " " << s.top() << "g\n";
p[s.top()].pb({R[i], w});
p[R[i]].pb({s.top(), w});
s.push(R[i]);
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
for(int i = 0; i < S; i ++) pq.push({dp[X[i]] = 0, X[i]});
while(!pq.empty()){
int w = pq.top().fi;
int u = pq.top().se;
pq.pop();
if(w > dp[u]) continue;
for(auto jj : p[u]){
int j = jj.fi;
int ts = jj.se;
if(dp[j] > dp[u] + ts) pq.push({dp[j] = dp[u] + ts, j});
}
}
for(int i = 0; i < T; i ++) ans = min(ans, dp[Y[i]]);
return ans;
}
//#define LOCAL
int A[N], B[N], C[N], X[N], Y[N], S, T;
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n >> q;
for(int i = 0; i < n - 1; i ++){
cin >> A[i] >> B[i] >> C[i];
}
Init(n, A, B, C);
while(q--){
cin >> S >> T;
for(int i = 0; i < S; i ++) cin >> X[i];
for(int i = 0; i < T; i ++) cin >> Y[i];
cout << Query(S, X, T, Y) << "\n";
}
}
#endif // LOCAL
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 1; i < vr.size(); i ++){
| ~~^~~~~~~~~~~
factories.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int i = 1; i < R.size(); i ++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
43356 KB |
Output is correct |
| 2 |
Correct |
1142 ms |
47908 KB |
Output is correct |
| 3 |
Correct |
1232 ms |
48116 KB |
Output is correct |
| 4 |
Incorrect |
1105 ms |
48152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
43352 KB |
Output is correct |
| 2 |
Correct |
1224 ms |
116020 KB |
Output is correct |
| 3 |
Incorrect |
2045 ms |
119696 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
43356 KB |
Output is correct |
| 2 |
Correct |
1142 ms |
47908 KB |
Output is correct |
| 3 |
Correct |
1232 ms |
48116 KB |
Output is correct |
| 4 |
Incorrect |
1105 ms |
48152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
