oj.uz

Submission #780097

# Submission time Handle Problem Language Result Execution time Memory
780097 2023-07-12T06:38:54 Z huutuan Factories (JOI14_factories) C++14
100 / 100
 2274 ms 454952 KB 
#include "factories.h"
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=5e5+1, LG=20;
int n, nvt, tdfs, st_cnt, tin[N], tout[N], dep[N], pos_st[N], dis[N], color[N];
pair<int, int> st[N*2][LG];
vector<pair<int, int>> g[N], vt[N];

void pre_dfs(int u, int p){
    tin[u]=++tdfs;
    st[++st_cnt][0]={dep[u], u};
    pos_st[u]=st_cnt;
    for (auto& e:g[u]){
        int v=e.first, w=e.second;
        if (v==p) continue;
        dep[v]=dep[u]+1;
        dis[v]=dis[u]+w;
        pre_dfs(v, u);
        st[++st_cnt][0]={dep[u], u};
    }
    tout[u]=tdfs;
}

void build_st(){
    for (int k=1; k<LG; ++k){
        for (int l=1; l+(1<<k)-1<=st_cnt; ++l){
            st[l][k]=min(st[l][k-1], st[l+(1<<(k-1))][k-1]);
        }
    }
}

int lca(int u, int v){
    u=pos_st[u], v=pos_st[v];
    if (u>v) swap(u, v);
    int lg=__lg(v-u+1);
    return min(st[u][lg], st[v-(1<<lg)+1][lg]).second;
}

bool is_ancestor(int u, int v){
    return tin[u]<=tin[v] && tin[v]<=tout[u];
}

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    memset(color, -1, sizeof color);
    n=N;
    for (int i=0; i<n-1; ++i){
        ++A[i]; ++B[i];
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }
    pre_dfs(1, 0);
    build_st();
}

pair<int, int> dfs(int u, int p, int& ans){
    pair<int, int> wtf={1e18, 1e18};
    if (color[u]==0) wtf.first=0;
    else if (color[u]==1) wtf.second=0;
    for (auto& e:vt[u]){
        int v=e.first, w=e.second;
        if (v==p) continue;
        auto lmao=dfs(v, u, ans);
        wtf.first=min(wtf.first, lmao.first+w);
        wtf.second=min(wtf.second, lmao.second+w);
    }
    ans=min(ans, wtf.first+wtf.second);
    return wtf;
}

long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    vector<int> vtn;
    for (int i=0; i<S; ++i) ++X[i], color[X[i]]=0;
    for (int i=0; i<T; ++i) ++Y[i], color[Y[i]]=1;
    for (int i=0; i<S; ++i) vtn.push_back(X[i]);
    for (int i=0; i<T; ++i) vtn.push_back(Y[i]);
    sort(all(vtn), [&](int u, int v) -> bool {
        return tin[u]<tin[v];
    });
    for (int i=0; i<S+T-1; ++i) vtn.push_back(lca(vtn[i], vtn[i+1]));
    sort(all(vtn), [&](int u, int v) -> bool {
        return tin[u]<tin[v];
    });
    vtn.resize(unique(all(vtn))-vtn.begin());
    for (int i:vtn) vt[i].clear();
    stack<int> st;
    for (int i:vtn){
        while (st.size() && !is_ancestor(st.top(), i)) st.pop();
        if (st.empty()) st.push(i);
        else{
            vt[st.top()].emplace_back(i, dis[i]-dis[st.top()]);
            vt[i].emplace_back(st.top(), dis[i]-dis[st.top()]);
            st.push(i);
        }
    }
    int ans=1e18;
    dfs(vtn[0], 0, ans);
    for (int i=0; i<S; ++i) color[X[i]]=-1;
    for (int i=0; i<T; ++i) color[Y[i]]=-1;
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28468 KB Output is correct
2 Correct 559 ms 39712 KB Output is correct
3 Correct 548 ms 39744 KB Output is correct
4 Correct 546 ms 39760 KB Output is correct
5 Correct 509 ms 40024 KB Output is correct
6 Correct 400 ms 39648 KB Output is correct
7 Correct 547 ms 39640 KB Output is correct
8 Correct 560 ms 39856 KB Output is correct
9 Correct 523 ms 40028 KB Output is correct
10 Correct 372 ms 39628 KB Output is correct
11 Correct 534 ms 39644 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28184 KB Output is correct
2 Correct 1237 ms 412928 KB Output is correct
3 Correct 1310 ms 417128 KB Output is correct
4 Correct 1096 ms 410344 KB Output is correct
5 Correct 1288 ms 452028 KB Output is correct
6 Correct 1382 ms 418752 KB Output is correct
7 Correct 818 ms 114376 KB Output is correct
8 Correct 640 ms 113520 KB Output is correct
9 Correct 722 ms 120016 KB Output is correct
10 Correct 769 ms 115548 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28468 KB Output is correct
2 Correct 559 ms 39712 KB Output is correct
3 Correct 548 ms 39744 KB Output is correct
4 Correct 546 ms 39760 KB Output is correct
5 Correct 509 ms 40024 KB Output is correct
6 Correct 400 ms 39648 KB Output is correct
7 Correct 547 ms 39640 KB Output is correct
8 Correct 560 ms 39856 KB Output is correct
9 Correct 523 ms 40028 KB Output is correct
10 Correct 372 ms 39628 KB Output is correct
11 Correct 534 ms 39644 KB Output is correct
12 Correct 15 ms 28184 KB Output is correct
13 Correct 1237 ms 412928 KB Output is correct
14 Correct 1310 ms 417128 KB Output is correct
15 Correct 1096 ms 410344 KB Output is correct
16 Correct 1288 ms 452028 KB Output is correct
17 Correct 1382 ms 418752 KB Output is correct
18 Correct 818 ms 114376 KB Output is correct
19 Correct 640 ms 113520 KB Output is correct
20 Correct 722 ms 120016 KB Output is correct
21 Correct 769 ms 115548 KB Output is correct
22 Correct 2213 ms 424812 KB Output is correct
23 Correct 1936 ms 423776 KB Output is correct
24 Correct 2274 ms 429852 KB Output is correct
25 Correct 2215 ms 432768 KB Output is correct
26 Correct 2017 ms 422692 KB Output is correct
27 Correct 2178 ms 454952 KB Output is correct
28 Correct 1574 ms 419904 KB Output is correct
29 Correct 2052 ms 421424 KB Output is correct
30 Correct 2027 ms 420676 KB Output is correct
31 Correct 1898 ms 421228 KB Output is correct
32 Correct 1014 ms 123276 KB Output is correct
33 Correct 785 ms 117452 KB Output is correct
34 Correct 934 ms 113428 KB Output is correct
35 Correct 902 ms 113252 KB Output is correct
36 Correct 1072 ms 114152 KB Output is correct
37 Correct 993 ms 114000 KB Output is correct