Submission #498618

#	Time	Username	Problem	Language	Result	Execution time	Memory
498618		Mahfel	Factories (JOI14_factories)	C++17	100 / 100	5281 ms	226176 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const ll MXN = 5e5 + 20 , LOG = 20 , Inf = 1e17;
vector<pair<ll,ll>> adj[MXN] , virt[MXN];
ll sz[MXN] , h[MXN] , wg[MXN] , sttime[MXN] , par[LOG][MXN] , tme;
ll dis[MXN];
bool mark[MXN];
bool in_subtree(int v , int u) {
    return sttime[v] >= sttime[u] && sttime[v] < sttime[u] + sz[u];
}
void prep(int v , int dad , ll dadw) {
    sttime[v] = tme++;
    sz[v] = 1;
    h[v] = (dad == -1 ? 0 : h[dad]+1);
    wg[v] = (dad == -1 ? 0 : wg[dad] + dadw);
    par[0][v] = (dad == -1 ? v : dad);
    for(auto pr : adj[v]) {
        ll u = pr.first , w = pr.second;
        if(u == dad) continue;
        prep(u , v , w);
        sz[v] += sz[u];
    }
}
int kth_anc(int v , int k) {
    while(k > 0) {
        int x = __builtin_ctz(k);
        v = par[x][v];
        k -= (1 << x);
    }
    return v;
}
int LCA(int v , int u) {
    if(h[v] > h[u]) swap(v , u);
    u = kth_anc(u , h[u]-h[v]);
    if(v == u) return v;
    for(int i = LOG-1 ; i >= 0 ; i--) {
        if(par[i][v] != par[i][u]) {
            v = par[i][v]; u = par[i][u];
        }
    }
    return par[0][v];
}

void Init(int n , int v[] , int u[] , int w[]) {
    for(int i = 0 ; i < n-1 ; i++) {
        adj[v[i]].push_back({u[i] , w[i]});
        adj[u[i]].push_back({v[i] , w[i]});
    }
    prep(0 , -1 , 0);
    for(int i = 1 ; i < LOG ; i++) {
        for(int j = 0 ; j < n ; j++) {
            par[i][j] = par[i-1][par[i-1][j]];
        }
    }
}

long long Query(int s , int X[] , int t , int Y[]) {
    vector<int> A(s) , B(t) , V;
    for(int i = 0 ; i < s ; i++) {
        A[i] = X[i]; V.push_back(A[i]);
    }
    for(int i = 0 ; i < t ; i++) {
        B[i] = Y[i]; V.push_back(B[i]);
    }
    sort(V.begin() , V.end() , [&](int a , int b) {
        return sttime[a] < sttime[b];
    });
    int c = V.size();
    for(int i = 0 ; i < c-1 ; i++) {
        V.push_back(LCA(V[i] , V[i+1]));
    }
    sort(V.begin() , V.end() , [&](int a , int b) {
        return sttime[a] < sttime[b];
    });
    V.resize(unique(V.begin() , V.end())-V.begin());

    vector<int> stck;
    for(auto v : V) {
        while(stck.size() > 0 && !in_subtree(v , stck.back())) stck.pop_back();
        if(stck.size() > 0) {
            virt[stck.back()].push_back({v , wg[v]-wg[stck.back()]});
            virt[v].push_back({stck.back() , wg[v]-wg[stck.back()]});
        }
        stck.push_back(v);
    }

    set<pair<ll,ll>> st;
    for(auto v : V) dis[v] = Inf;
    for(auto v : A) {
        dis[v] = 0; st.insert({0 , v});
    }
    while(!st.empty()) {
        pair<ll,ll> p = *st.begin(); st.erase(p);
        ll v = p.second; mark[v] = 1;
        for(auto pr : virt[v]) {
            ll u = pr.first , w = pr.second;
            if(mark[u]) continue;
            st.erase({dis[u] , u});
            dis[u] = min(dis[u] , dis[v] + w);
            st.insert({dis[u] , u});
        }
    }

    ll ans = Inf;
    for(auto v : B) {
        ans = min(ans , dis[v]);
    }
    for(auto v : V) {
        virt[v].clear();
        dis[v] = 0;
        mark[v] = 0;
    }
    return ans;    
}

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