oj.uz

Submission #780003

# Submission time Handle Problem Language Result Execution time Memory
780003 2023-07-12T05:04:23 Z Antonn_114 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 392896 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;
        }
    }

    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 (!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 49 ms 64100 KB Output is correct
2 Correct 584 ms 74608 KB Output is correct
3 Correct 679 ms 74744 KB Output is correct
4 Correct 581 ms 74680 KB Output is correct
5 Correct 552 ms 75036 KB Output is correct
6 Correct 475 ms 74572 KB Output is correct
7 Correct 632 ms 74632 KB Output is correct
8 Correct 582 ms 74720 KB Output is correct
9 Correct 543 ms 75048 KB Output is correct
10 Correct 480 ms 74560 KB Output is correct
11 Correct 634 ms 74648 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63740 KB Output is correct
2 Execution timed out 8093 ms 392896 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 64100 KB Output is correct
2 Correct 584 ms 74608 KB Output is correct
3 Correct 679 ms 74744 KB Output is correct
4 Correct 581 ms 74680 KB Output is correct
5 Correct 552 ms 75036 KB Output is correct
6 Correct 475 ms 74572 KB Output is correct
7 Correct 632 ms 74632 KB Output is correct
8 Correct 582 ms 74720 KB Output is correct
9 Correct 543 ms 75048 KB Output is correct
10 Correct 480 ms 74560 KB Output is correct
11 Correct 634 ms 74648 KB Output is correct
12 Correct 33 ms 63740 KB Output is correct
13 Execution timed out 8093 ms 392896 KB Time limit exceeded
14 Halted 0 ms 0 KB -