oj.uz

Submission #498618

# Submission time Handle Problem Language Result Execution time Memory
498618 2021-12-25T19:47:32 Z Mahfel Factories (JOI14_factories) C++17
100 / 100
 5281 ms 226176 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24684 KB Output is correct
2 Correct 1535 ms 39684 KB Output is correct
3 Correct 1614 ms 39628 KB Output is correct
4 Correct 1516 ms 39800 KB Output is correct
5 Correct 1328 ms 39876 KB Output is correct
6 Correct 1018 ms 39400 KB Output is correct
7 Correct 1615 ms 39236 KB Output is correct
8 Correct 1520 ms 41352 KB Output is correct
9 Correct 1308 ms 42396 KB Output is correct
10 Correct 1036 ms 41948 KB Output is correct
11 Correct 1614 ms 42036 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24260 KB Output is correct
2 Correct 2013 ms 175076 KB Output is correct
3 Correct 2659 ms 179280 KB Output is correct
4 Correct 1309 ms 184740 KB Output is correct
5 Correct 2160 ms 226176 KB Output is correct
6 Correct 2794 ms 192828 KB Output is correct
7 Correct 3104 ms 71392 KB Output is correct
8 Correct 1484 ms 70592 KB Output is correct
9 Correct 1860 ms 77104 KB Output is correct
10 Correct 3081 ms 72540 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24684 KB Output is correct
2 Correct 1535 ms 39684 KB Output is correct
3 Correct 1614 ms 39628 KB Output is correct
4 Correct 1516 ms 39800 KB Output is correct
5 Correct 1328 ms 39876 KB Output is correct
6 Correct 1018 ms 39400 KB Output is correct
7 Correct 1615 ms 39236 KB Output is correct
8 Correct 1520 ms 41352 KB Output is correct
9 Correct 1308 ms 42396 KB Output is correct
10 Correct 1036 ms 41948 KB Output is correct
11 Correct 1614 ms 42036 KB Output is correct
12 Correct 16 ms 24260 KB Output is correct
13 Correct 2013 ms 175076 KB Output is correct
14 Correct 2659 ms 179280 KB Output is correct
15 Correct 1309 ms 184740 KB Output is correct
16 Correct 2160 ms 226176 KB Output is correct
17 Correct 2794 ms 192828 KB Output is correct
18 Correct 3104 ms 71392 KB Output is correct
19 Correct 1484 ms 70592 KB Output is correct
20 Correct 1860 ms 77104 KB Output is correct
21 Correct 3081 ms 72540 KB Output is correct
22 Correct 4911 ms 191792 KB Output is correct
23 Correct 4409 ms 190732 KB Output is correct
24 Correct 5281 ms 196192 KB Output is correct
25 Correct 5064 ms 197108 KB Output is correct
26 Correct 4805 ms 186108 KB Output is correct
27 Correct 3669 ms 219660 KB Output is correct
28 Correct 2880 ms 184140 KB Output is correct
29 Correct 4611 ms 183796 KB Output is correct
30 Correct 4683 ms 183632 KB Output is correct
31 Correct 4768 ms 183552 KB Output is correct
32 Correct 2601 ms 80508 KB Output is correct
33 Correct 2039 ms 75244 KB Output is correct
34 Correct 2910 ms 68392 KB Output is correct
35 Correct 2843 ms 69040 KB Output is correct
36 Correct 3069 ms 69756 KB Output is correct
37 Correct 3231 ms 69732 KB Output is correct