Submission #1243166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243166		hoangmc2009	Factories (JOI14_factories)	C++17	100 / 100	3981 ms	164884 KiB

factories

#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 Init(int N,int A[],int B[],int D[])
{
    n=N;
    for(int i=0;i<n-1;++i)
    {
        ++A[i]; ++B[i];
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    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]];
}
i64 Query(int S,int X[],int T,int Y[])
{
    i64 res=9e18;
    vector<int> Z(S+T);
    for(int i=0;i<S;++i) Z[i]=++X[i];
    for(int i=0;i<T;++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<S;++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<T;++i) res=min(res,mindist[Y[i]]);
    for(int i=0;i<Z.size();++i) bdj[Z[i]].clear();
    return res;
}
// No Raven here :((, cuz size limit exceeded

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67