oj.uz

Submission #780000

# Submission time Handle Problem Language Result Execution time Memory
780000 2023-07-12T05:01:33 Z Antonn_114 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 393004 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;
}
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;
    }else 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 40 ms 63948 KB Output is correct
2 Correct 555 ms 74524 KB Output is correct
3 Correct 619 ms 74444 KB Output is correct
4 Correct 563 ms 74548 KB Output is correct
5 Correct 503 ms 74920 KB Output is correct
6 Correct 449 ms 74432 KB Output is correct
7 Correct 619 ms 74504 KB Output is correct
8 Correct 577 ms 74568 KB Output is correct
9 Correct 511 ms 74944 KB Output is correct
10 Correct 450 ms 74508 KB Output is correct
11 Correct 666 ms 74564 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63672 KB Output is correct
2 Execution timed out 8029 ms 393004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 63948 KB Output is correct
2 Correct 555 ms 74524 KB Output is correct
3 Correct 619 ms 74444 KB Output is correct
4 Correct 563 ms 74548 KB Output is correct
5 Correct 503 ms 74920 KB Output is correct
6 Correct 449 ms 74432 KB Output is correct
7 Correct 619 ms 74504 KB Output is correct
8 Correct 577 ms 74568 KB Output is correct
9 Correct 511 ms 74944 KB Output is correct
10 Correct 450 ms 74508 KB Output is correct
11 Correct 666 ms 74564 KB Output is correct
12 Correct 32 ms 63672 KB Output is correct
13 Execution timed out 8029 ms 393004 KB Time limit exceeded
14 Halted 0 ms 0 KB -