oj.uz

Submission #779962

# Submission time Handle Problem Language Result Execution time Memory
779962 2023-07-12T04:07:41 Z Antonn_114 Factories (JOI14_factories) C++14
0 / 100
 8000 ms 395092 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], visited[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 (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();

}
long long Query(int S, int X[], int T, int Y[]) {
    res_query = INF;
    vector<int> a;
    memset(visited, 0, sizeof visited);
    memset(mark1, 0, sizeof mark1);
    memset(mark2, 0, sizeof mark2);
    fill(begin(dp1), end(dp1), INF);
    fill(begin(dp2), end(dp2), INF);
    for (int i = 0; i < S; i++){
        mark1[X[i]] = 1;
    }
    for (int i = 0; i < T; i++){
        mark2[Y[i]] = 1;
    }
    for (int i = 0; i < n; i++){
        if (mark1[i] || mark2[i]){
            a.push_back(i);visited[i] = 1;
        }
    }
    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];
    });
    int old_sz = a.size();
    for (int i = 0; i < old_sz - 1; i ++){
        int lca = LCA(a[i], a[i + 1]).second;
        if (!visited[lca]){
            a.push_back(lca);
            visited[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});
            g_aux[a[i]].push_back({u, w});
        }
        st.push(a[i]);
    }
    dfs2(a[0], -1);
    return res_query;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 66816 KB Output is correct
2 Correct 7602 ms 77360 KB Output is correct
3 Execution timed out 8085 ms 77296 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 66636 KB Output is correct
2 Execution timed out 8036 ms 395092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 66816 KB Output is correct
2 Correct 7602 ms 77360 KB Output is correct
3 Execution timed out 8085 ms 77296 KB Time limit exceeded
4 Halted 0 ms 0 KB -