oj.uz

Submission #779990

# Submission time Handle Problem Language Result Execution time Memory
779990 2023-07-12T04:54:35 Z Antonn_114 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 398980 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});
            g_aux[a[i]].push_back({u, 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 42 ms 67792 KB Output is correct
2 Correct 595 ms 78244 KB Output is correct
3 Correct 700 ms 78284 KB Output is correct
4 Correct 628 ms 78308 KB Output is correct
5 Correct 545 ms 78760 KB Output is correct
6 Correct 468 ms 78164 KB Output is correct
7 Correct 695 ms 78296 KB Output is correct
8 Correct 612 ms 78460 KB Output is correct
9 Correct 549 ms 78624 KB Output is correct
10 Correct 480 ms 78116 KB Output is correct
11 Correct 677 ms 78288 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 67792 KB Output is correct
2 Correct 595 ms 78244 KB Output is correct
3 Correct 700 ms 78284 KB Output is correct
4 Correct 628 ms 78308 KB Output is correct
5 Correct 545 ms 78760 KB Output is correct
6 Correct 468 ms 78164 KB Output is correct
7 Correct 695 ms 78296 KB Output is correct
8 Correct 612 ms 78460 KB Output is correct
9 Correct 549 ms 78624 KB Output is correct
10 Correct 480 ms 78116 KB Output is correct
11 Correct 677 ms 78288 KB Output is correct
12 Correct 33 ms 67516 KB Output is correct
13 Execution timed out 8060 ms 398980 KB Time limit exceeded
14 Halted 0 ms 0 KB -