Submission #1064941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064941		dpsaveslives	Factories (JOI14_factories)	C++17	100 / 100	3156 ms	189980 KiB

factories

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int MAXN = 5e5+10;
vector<pair<int,ll>> adj[MAXN],newg[MAXN];
int par[MAXN][21],in[MAXN],out[MAXN];
ll dist[MAXN],distr[MAXN];
vector<int> dep;
int timer;
const ll INF = 1e18;
void dfs(int u, int p){
    in[u] = ++timer;
    par[u][0] = p;
    for(auto edg : adj[u]){
        if(edg.f != p){
            distr[edg.f] = distr[u]+edg.s;
            dfs(edg.f,u);
        }
    }
    out[u] = timer;
}
bool anc(int a, int b){
    return in[a] <= in[b] && out[a] >= out[b];
}
bool cmp(int a, int b){
    return in[a] < in[b];
}
void Init(int N, int A[], int B[], int D[]){
    for(int i = 0;i<=N-2;++i){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    dfs(0,0);
    for(int i = 1;i<=20;++i){
        for(int j = 0;j<=N-1;++j){
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }
    for(int i = 0;i<=N-1;++i){
        dist[i] = INF;
    }
}
int lca(int a, int b){
    if(anc(a,b)) return a;
    if(anc(b,a)) return b;
    for(int i = 20;i>=0;--i){
        if(!anc(par[a][i],b)) a = par[a][i];
    }
    return par[a][0];
}
ll Query(int S, int X[], int T, int Y[]){
    vector<int> LS;
    for(int i = 0;i<S;++i){
        LS.push_back(X[i]);
    }
    for(int i = 0;i<T;++i){
        LS.push_back(Y[i]);
    }
    sort(LS.begin(),LS.end(),cmp); //sorted by DFS order
    for(int i = 0;i<=S+T-2;++i){
        LS.push_back(lca(LS[i],LS[i+1]));
    }
    LS.push_back(0);
    sort(LS.begin(),LS.end(),cmp);
    LS.resize(unique(LS.begin(),LS.end())-LS.begin());
    vector<int> st;
    for(int i = 0;i<LS.size();++i){
        while(!st.empty() && !anc(st.back(),LS[i])) st.pop_back();
        if(st.size()){
            newg[st.back()].push_back({LS[i],distr[LS[i]]-distr[st.back()]});
            newg[LS[i]].push_back({st.back(),distr[LS[i]]-distr[st.back()]});
        }
        st.push_back(LS[i]);
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    for(int i = 0;i<S;++i){
        pq.push({0ll,X[i]});
        dist[X[i]] = 0ll;
    }
    while(!pq.empty()){
        int u = pq.top().s; ll cd = pq.top().f; pq.pop();
        if(cd != dist[u]) continue;
        for(auto x : newg[u]){
            if(cd+x.s < dist[x.f]){
                dist[x.f] = cd+x.s;
                pq.push({dist[x.f],x.f});
            }
        }
    }
    ll ret = INF;
    for(int i = 0;i<T;++i){
        ret = min(ret,dist[Y[i]]);
    }
    for(int i = 0;i<LS.size();++i){
        dist[LS[i]] = INF;
        newg[LS[i]].clear();
    }
    return ret;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0;i<LS.size();++i){
      |                   ~^~~~~~~~~~
factories.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0;i<LS.size();++i){
      |                   ~^~~~~~~~~~

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