oj.uz

Submission #779996

# Submission time Handle Problem Language Result Execution time Memory
779996 2023-07-12T04:58:07 Z Antonn_114 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 395500 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;
int mark[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;
}
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 (mark[u] == 2){
        dp2[u] = 0;
    }else if (mark[u] == 1){
        dp1[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);
    memset(mark, 0, sizeof mark);

}
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]);
        mark[X[i]] = 1;
    }
    for (int i = 0; i < T; i++){
        a.push_back(Y[i]);
        mark[Y[i]] = 2;
    }

    for (int i = 0; i < n; i++){
        g_aux[i].clear();
    }
    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 (!mark[lca]){
            a.push_back(lca);
            mark[lca] = 3;
        }
    }
    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;
        mark[i] = 0;
        g_aux[i].clear();
    }
    return res_query;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 67980 KB Output is correct
2 Correct 565 ms 78876 KB Output is correct
3 Correct 636 ms 78892 KB Output is correct
4 Correct 631 ms 78976 KB Output is correct
5 Correct 527 ms 79316 KB Output is correct
6 Correct 457 ms 78808 KB Output is correct
7 Correct 678 ms 78916 KB Output is correct
8 Correct 623 ms 78964 KB Output is correct
9 Correct 524 ms 79320 KB Output is correct
10 Correct 456 ms 78928 KB Output is correct
11 Correct 636 ms 79020 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 67532 KB Output is correct
2 Execution timed out 8080 ms 395500 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 67980 KB Output is correct
2 Correct 565 ms 78876 KB Output is correct
3 Correct 636 ms 78892 KB Output is correct
4 Correct 631 ms 78976 KB Output is correct
5 Correct 527 ms 79316 KB Output is correct
6 Correct 457 ms 78808 KB Output is correct
7 Correct 678 ms 78916 KB Output is correct
8 Correct 623 ms 78964 KB Output is correct
9 Correct 524 ms 79320 KB Output is correct
10 Correct 456 ms 78928 KB Output is correct
11 Correct 636 ms 79020 KB Output is correct
12 Correct 41 ms 67532 KB Output is correct
13 Execution timed out 8080 ms 395500 KB Time limit exceeded
14 Halted 0 ms 0 KB -