Submission #1243139

#TimeUsernameProblemLanguageResultExecution timeMemory
1243139hoangmc2009Factories (JOI14_factories)C++17
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()
{
    if(fopen("D:/CPP/THEMIS/test.inp","r"))
    {
        freopen("D:/CPP/THEMIS/test.inp","r",stdin);
        freopen("D:/CPP/THEMIS/test.out","w",stdout);
    }
    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)

factories.cpp: In function 'int main()':
factories.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("D:/CPP/THEMIS/test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("D:/CPP/THEMIS/test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccm6ZSdx.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccRG5dqU.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccm6ZSdx.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