| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 335192 | cgiosy | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct iw { int i, w; };
struct __attribute__((packed)) ix { int i; ll x; };
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, Q;
cin>>N>>Q;
vector<int> C(N, 1), P(N), H(N);
vector<ll> D(N), R(Q, 1e18);
vector<vector<iw>> G(N);
vector<array<vector<int>, 2>> X(N);
vector<array<vector<ix>, 2>> T(Q);
for(int i=1; i<N; i++) {
int x, y, w;
cin>>x>>y>>w;
G[x].push_back({y, w});
G[y].push_back({x, w});
}
for(int i=0; i<Q; i++) {
int n, m;
cin>>n>>m;
for(int j=0; j<n+m; j++) {
int x;
cin>>x;
X[x][j>=n].push_back(i);
}
}
function<void(int)> count=[&](int i) {
for(iw&p:G[i]) if(p.i!=P[i]) {
D[p.i]=D[i]+p.w, P[p.i]=i, count(p.i), C[i]+=C[p.i];
if(iw&q=G[i][0]; C[p.i]>C[q.i]) swap(p, q);
}
};
auto lca=[&](int i, int j) {
while(H[i]!=H[j]) {
if(D[H[i]]<D[H[j]]) swap(i, j);
i=P[H[i]];
}
return D[i]<D[j] ? i : j;
};
function<void(int)> dfs=[&](int i) {
for(int f=0; f<2; f++) for(int k:X[i][f]) {
auto&s=T[k][f^1];
int t=(int)s.size()-1;
if(t>=0) {
s[t].i=lca(s[t].i, i);
while(t>0) {
s[t-1].i=lca(s[t-1].i, s[t].i);
if(s[t-1].x-2*D[s[t-1].i] > s[t].x-2*D[s[t].i]) break;
s.pop_back(), t--;
}
R[k]=min(R[k], D[i]+s[t].x-2*D[s[t].i]);
}
T[k][f].push_back({i, D[i]});
}
for(auto[j,w]:G[i]) if(j!=P[i])
H[j]=j==G[i][0].i ? H[i] : j, dfs(j);
};
count(0);
dfs(0);
for(ll x:R) cout<<x<<'\n';
}