| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126146 | ntdaccode | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;
typedef pair<long long,long long> ii;
typedef tuple<int,int,int> tp;
const int M = 5e5 + 10;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, q;
vector<ii> ke[M];
int num[M], tail[M], cnt = 0, up[M][20];
long long d[M];
void dfs(int u,int p = 0)
{
num[u] = ++ cnt;
for(int i = 1;i <= 19; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for(ii tmp : ke[u]) {
int v = tmp.first;
long long w = tmp.second;
if(v == p) continue;
d[v] = d[u] + w;
up[v][0] = u;
dfs(v,u);
}
tail[u] = cnt;
}
bool anc(int u,int v)
{
return num[u] <= num[v] && tail[u] >= tail[v];
}
int lca(int u,int v)
{
if(anc(u,v)) return u;
if(anc(v,u)) return v;
for(int i = 19; i >= 0; i--) if(!anc(up[u][i],v)) u = up[u][i];
return up[u][0];
}
long long D[M];
bool cmp(const int &a,const int &b) {
return num[a] < num[b];
}
bool dd[M];
void Init(int N, int A[], int B[], int DD[]) {
n = N;
for(int i = 0;i < n - 1; i++) {
int u = A[i], v = B[i];
long long w = DD[i];
u ++, v ++;
ke[u].pb({v,w});
ke[v].pb({u,w});
}
up[1][0] = 1;
dfs(1,0);
for(int i = 1;i <= n; i++) ke[i].clear();
for(int i = 1;i <= n; i++) D[i] = 1e15;
}
stack<int> sk;
vector<int> Q;
priority_queue<ii, vector<ii>, greater<ii> > h;
long long Query(int S, int X[], int T, int Y[]){
bool ok = 0;
for(int i = 0;i < S; i++) {
X[i]++;
int u = X[i];
dd[u] = true;
// cout << u << " ";
Q.pb(u);
}
for(int i = 0;i < T; i++) {
Y[i]++;
int u = Y[i];
if(dd[u]) {
ok = 1;
break;
}
dd[u] = true;
Q.pb(u);
}
if(ok == 1) {
for(int v : Q) dd[v] = false;
Q.clear();
return 0;
}
sort(Q.begin(), Q.end(),cmp);
Q.resize(unique(Q.begin(), Q.end()) - Q.begin());
int m = Q.size();
for(int i = 1;i <= m - 1; i++) {
int x = lca(Q[i - 1],Q[i]);
if(!dd[x]) Q.pb(x);
dd[x] = true;
}
sort(Q.begin(), Q.end(), cmp);
for(int v : Q) {
while(!sk.empty() && !anc(sk.top(),v)) sk.pop();
if(!sk.empty()) {
long long w = d[v] - d[sk.top()];
ke[v].pb({sk.top(),w});
ke[sk.top()].pb({v,w});
}
sk.push(v);
}
while(!sk.empty()) {
int v = sk.top();sk.pop();
if(!sk.empty()) {
int w = d[v] - d[sk.top()];
ke[v].pb({sk.top(),w});
ke[sk.top()].pb({v,w});
}
}
for(int i = 0;i < S; i++) {
int v = X[i];
D[v] = 0;
h.push({0,v});
}
while(!h.empty()) {
int u;
long long val;
tie(val,u) = h.top();h.pop();
if(D[u] < val) continue;
for(ii tmp : ke[u]) {
int v = tmp.first;
long long w = tmp.second;
if(D[v] > D[u] + w) {
D[v] = D[u] + w;
h.push({D[v],v});
}
}
}
long long kq = 1e15;
for(int i = 0;i < T; i++) kq = min(kq, D[Y[i]]);
for(int v : Q) {
ke[v].clear();
D[v] = 1e15;
dd[v] = false;
}
Q.clear();
while(!sk.empty()) sk.pop();
return kq;
}
#define LOCAL
#ifdef LOCAL
int uu[M], vv[M], ww[M];
int xx[M], yy[M];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r")) {
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
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 >> uu[i] >> vv[i] >> ww[i];
}
Init(n,uu,vv,ww);
while(q--) {
int s,t;
cin >> s >> t;
for(int i = 0;i < s; i++) cin >> xx[i];
for(int i = 0;i < t; i++) cin >> yy[i];
cout << Query(s,xx,t,yy) << "\n";
}
}
#endif