oj.uz

Submission #780006

# Submission time Handle Problem Language Result Execution time Memory
780006 2023-07-12T05:08:29 Z Antonn_114 Factories (JOI14_factories) C++14
100 / 100
 3278 ms 446908 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int lg2(unsigned long long i) { return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1; }
const int NM = 1e6+6;
vector<pair<int, long long>> g[NM];
vector<pair<int, long long>> g_aux[NM]; 
int t_in[NM];
int t_out[NM];
pair<int, int> sp[21][NM];
int up[21][NM];
long long up_dist[21][NM];
const long long INF = 1e18+5;
int n;
vector<pair<int, int>> euler_tour;
bool mark1[NM], mark2[NM], vis[NM];
long long res_query = INF;
long long dp1[NM], dp2[NM];
void dfs(int u, int p, int d){
    t_in[u] = euler_tour.size();
    up[0][u] = p;
    for (int i = 1; i <= 20; i++){
        up[i][u] = up[i - 1][up[i - 1][u]];
        up_dist[i][u] = up_dist[i - 1][u] + up_dist[i - 1][up[i - 1][u]];
    }
    euler_tour.push_back({d, u});
    for (auto& e : g[u]){
        int &v = e.first;
        long long &w = e.second;
        if (v == p) continue;
        up_dist[0][v] = w;
        dfs(v, u, d + 1);
        euler_tour.push_back({d, u});
    }
    t_out[u] = euler_tour.size() - 1;
}
inline void build_sparse_table(){
    for (int i = 0; i < (int)euler_tour.size(); i++){
        sp[0][i] = euler_tour[i];
    }
    for (int i = 1; i <= 20; i++){
        for (int j = 0; j < (int)euler_tour.size() - (1 << (i - 1)); j++){
            sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
        }
    }
}
inline pair<int, int> LCA(int u, int v){
    int l = t_in[u];
    int r = t_in[v];
    if (l > r) swap(l, r);
    int lvl = lg2(r - l + 1);
    return min(sp[lvl][l], sp[lvl][r - (1 << lvl) + 1]);
}
inline long long dist_to_ancestor(int u, int v){
    int dept = euler_tour[t_in[u]].first - euler_tour[t_in[v]].first;
    long long res = 0;
    for (int i = 20; i >= 0; i--){
        if ((dept >> i) & 1){
            res += up_dist[i][u];
            u = up[i][u];
        }
    }
    return res;
}


void dfs2(int u, int p){
    if (mark1[u]){
        dp1[u] = 0;
    }
    if (mark2[u]){
        dp2[u] = 0;
    }
    for (auto v : g_aux[u]){
        if (v.first == p) continue;
        dfs2(v.first, u);
        res_query = min(res_query, min(dp1[u] + dp2[v.first] + v.second, dp2[u] + dp1[v.first]+ v.second));
        dp1[u] = min(dp1[u], dp1[v.first] + v.second);
        dp2[u] = min(dp2[u], dp2[v.first] + v.second);
    }
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < N; i++){
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0, 0);
    build_sparse_table();
    fill(begin(dp1), end(dp1), INF);
    fill(begin(dp2), end(dp2), INF);

}
long long Query(int S, int X[], int T, int Y[]) {
    res_query = INF;
    vector<int> a;
    for (int i = 0; i < S; i++){
        a.push_back(X[i]);
        mark1[X[i]] = 1;
        vis[X[i]] = 1;
    }
    for (int i = 0; i < T; i++){
        mark2[Y[i]] = 1;
        if (!vis[Y[i]]){
            a.push_back(Y[i]);
            vis[Y[i]] = 1;
        }
    }
    sort(a.begin(), a.end(), [&](const int &x, const int &y){
            return t_in[x] < t_in[y];
            });
    for (int i = 0; i < S + T - 1; i ++){
        int lca = LCA(a[i], a[i + 1]).second;
        if (!vis[lca]){
            a.push_back(lca);
            vis[lca] = 1;
        }
    }
    sort(a.begin(), a.end(), [&](const int &x, const int &y){
            return t_in[x] < t_in[y];
            });
    stack<int> st;
    for (int i = 0; i < int(a.size()); i++){
        while(!st.empty() && t_out[st.top()] <= t_in[a[i]]){
            st.pop();
        }
        if (st.empty()){
            st.push(a[i]);
            continue;
        }
        int u = st.top();
        if (u != a[i]){
            long long w = dist_to_ancestor(a[i], u);
            g_aux[u].push_back({a[i], w});
        }
        st.push(a[i]);
    }
    dfs2(a[0], -1);
    for (auto& i : a){
        dp1[i] = dp2[i] = INF;
        mark1[i] = mark2[i] = vis[i] = 0;
        g_aux[i].clear();
    }
    return res_query;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63828 KB Output is correct
2 Correct 540 ms 74732 KB Output is correct
3 Correct 603 ms 74880 KB Output is correct
4 Correct 566 ms 74808 KB Output is correct
5 Correct 491 ms 75208 KB Output is correct
6 Correct 435 ms 74696 KB Output is correct
7 Correct 611 ms 74776 KB Output is correct
8 Correct 574 ms 74912 KB Output is correct
9 Correct 495 ms 75264 KB Output is correct
10 Correct 428 ms 74700 KB Output is correct
11 Correct 609 ms 74772 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 63640 KB Output is correct
2 Correct 1483 ms 394584 KB Output is correct
3 Correct 2139 ms 400860 KB Output is correct
4 Correct 1134 ms 392236 KB Output is correct
5 Correct 2321 ms 446908 KB Output is correct
6 Correct 2304 ms 401980 KB Output is correct
7 Correct 1389 ms 136796 KB Output is correct
8 Correct 634 ms 135952 KB Output is correct
9 Correct 1355 ms 144424 KB Output is correct
10 Correct 1443 ms 138000 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63828 KB Output is correct
2 Correct 540 ms 74732 KB Output is correct
3 Correct 603 ms 74880 KB Output is correct
4 Correct 566 ms 74808 KB Output is correct
5 Correct 491 ms 75208 KB Output is correct
6 Correct 435 ms 74696 KB Output is correct
7 Correct 611 ms 74776 KB Output is correct
8 Correct 574 ms 74912 KB Output is correct
9 Correct 495 ms 75264 KB Output is correct
10 Correct 428 ms 74700 KB Output is correct
11 Correct 609 ms 74772 KB Output is correct
12 Correct 30 ms 63640 KB Output is correct
13 Correct 1483 ms 394584 KB Output is correct
14 Correct 2139 ms 400860 KB Output is correct
15 Correct 1134 ms 392236 KB Output is correct
16 Correct 2321 ms 446908 KB Output is correct
17 Correct 2304 ms 401980 KB Output is correct
18 Correct 1389 ms 136796 KB Output is correct
19 Correct 634 ms 135952 KB Output is correct
20 Correct 1355 ms 144424 KB Output is correct
21 Correct 1443 ms 138000 KB Output is correct
22 Correct 2342 ms 405304 KB Output is correct
23 Correct 2315 ms 407360 KB Output is correct
24 Correct 2693 ms 411160 KB Output is correct
25 Correct 2858 ms 415784 KB Output is correct
26 Correct 3028 ms 404620 KB Output is correct
27 Correct 2915 ms 446588 KB Output is correct
28 Correct 1734 ms 401452 KB Output is correct
29 Correct 3278 ms 403008 KB Output is correct
30 Correct 3259 ms 402304 KB Output is correct
31 Correct 3216 ms 402996 KB Output is correct
32 Correct 1029 ms 146472 KB Output is correct
33 Correct 716 ms 138352 KB Output is correct
34 Correct 1037 ms 135608 KB Output is correct
35 Correct 1052 ms 135400 KB Output is correct
36 Correct 1347 ms 136456 KB Output is correct
37 Correct 1269 ms 136520 KB Output is correct