Submission #1243146

#TimeUsernameProblemLanguageResultExecution timeMemory
1243146nai0610Factories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; i64 n,q,dist[500009],mindist[500009]; int _t=0,tin[500009],tout[500009],par[20][500009]; vector<pair<int,i64>> adj[500009],bdj[500009]; void DFS(int u,int pu,i64 d) { tin[u]=++_t; dist[u]=d; par[0][u]=pu; for(auto& v:adj[u]) if(v.first!=pu) DFS(v.first,u,d+v.second); tout[u]=_t; } bool isA(int u,int v) {return tin[u]<=tin[v] and tout[v]<=tout[u];} int LCA(int u,int v) { if(isA(u,v)) return u; if(isA(v,u)) return v; for(int i=19;i>=0;--i) if(!isA(par[i][u],v)) u=par[i][u]; return par[0][u]; } //i64 dist2(int u,int v) {return dist[u]+dist[v]-2*dist[LCA(u,v)];} void xl() { int S,T; cin>>S>>T; i64 res=9e18; vector<int> X(S),Y(T),Z(S+T); for(int i=0;i<S;++i) {cin>>X[i]; Z[i]=++X[i];} for(int i=0;i<T;++i) {cin>>Y[i]; Z[i+S]=++Y[i];} sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];}); for(int i=1;i<S+T;++i) Z.push_back(LCA(Z[i],Z[i-1])); sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];}); Z.resize(distance(Z.begin(),unique(Z.begin(),Z.end()))); stack<int> st; st.push(Z[0]); mindist[Z[0]]=3e18; for(int i=1;i<Z.size();++i) { while(!isA(st.top(),Z[i])) st.pop(); bdj[st.top()].push_back({Z[i],dist[Z[i]]-dist[st.top()]}); bdj[Z[i]].push_back({st.top(),dist[Z[i]]-dist[st.top()]}); st.push(Z[i]); mindist[Z[i]]=3e18; } set<pair<i64,int>> dij; for(int i=0;i<X.size();++i) { mindist[X[i]]=0; dij.insert({0,X[i]}); } while(!dij.empty()) { int u=dij.begin()->second; dij.erase(dij.begin()); for(auto& v:bdj[u]) { if(mindist[v.first]>mindist[u]+v.second) { dij.erase({mindist[v.first],v.first}); mindist[v.first]=mindist[u]+v.second; dij.insert({mindist[v.first],v.first}); } } } for(int i=0;i<Y.size();++i) res=min(res,mindist[Y[i]]); for(int i=0;i<Z.size();++i) bdj[Z[i]].clear(); cout<<res<<'\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for(int u,v,w,i=1;i<n;++i) { cin>>u>>v>>w; ++u; ++v; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } DFS(1,0,0); par[0][1]=1; for(int i=1;i<20;++i) for(int j=1;j<=n;++j) par[i][j]=par[i-1][par[i-1][j]]; while(q--) xl(); } // No Raven here :((, cuz size limit exceeded

Compilation message (stderr)

/usr/bin/ld: /tmp/ccNMaU9X.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyf8gsL.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccNMaU9X.o: in function `main':
grader.cpp:(.text.startup+0x3d5): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x468): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status