oj.uz

Submission #780219

# Submission time Handle Problem Language Result Execution time Memory
780219 2023-07-12T07:20:36 Z cheat_when_I_was_young Factories (JOI14_factories) C++17
15 / 100
 1138 ms 310904 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int NM = 5e5 + 5;
const int LG = __lg(NM) + 1;
int in[NM], h[NM], color[NM], par[NM];
long long d[NM], dp[NM][3], ans;
pair<int,int> ST[LG][NM];
vector<int> tour, newAdj[NM];
vector<pair<int,int>> adj[NM];

void dfs(int u, int par) {
    in[u] = tour.size();
    tour.push_back(u);
    for (auto &vv: adj[u]) {
        int v = vv.first, w = vv.second;
        if (v == par) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
        tour.push_back(u);
    }
}

void build() {
    for (int i = 0; i < (int)tour.size(); ++i)
        ST[0][i] = {h[tour[i]], tour[i]};
    for (int j = 1; j < LG; ++j)
        for (int i = 0; i + (1<<j) - 1 < (int)tour.size(); ++i)
            ST[j][i] = min(ST[j-1][i], ST[j-1][i + (1<<(j-1))]);
}

int lca(int u, int v) {
    int l = in[u], r = in[v];
    if (l > r) swap(l, r);
    int k = __lg(r - l + 1);
    return min(ST[k][l], ST[k][r - (1<<k) + 1]).second;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++i) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    build();
    ans = 1e18;
    for (int i = 0; i < N; ++i) {
        par[i] = -1;
        dp[i][1] = dp[i][2] = 1e18;
    }
}

void DFS(int u, int par) {
    for (int &v: newAdj[u]) {
        if (v == par) continue;
        DFS(v, u);
    }
    if (color[u]) dp[u][color[u]] = 0;
    for (int &v: newAdj[u]) {
        if (v == par) continue;
        if (!color[v]) {
            dp[u][1] = min(dp[u][1], dp[v][1] + d[v] - d[u]);
            dp[u][2] = min(dp[u][2], dp[v][2] + d[v] - d[u]);
        } else dp[u][color[v]] = min(dp[u][color[v]], d[v] - d[u]);
    }
    ans = min(ans, dp[u][1] + dp[u][2]);
}

auto cmp = [](int x, int y) {
    return in[x] < in[y];
};

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) color[X[i]] = 1;
    for (int i = 0; i < T; ++i) {
        if (color[Y[i]] == 1) {
            for (int j = 0; j < S; ++j) color[X[j]] = 0;
            for (int j = 0; j < T; ++j) color[Y[j]] = 0;
            return 0;
        }
        color[Y[i]] = 2;
    }
    set<int, decltype(cmp)> node(cmp);
    stack<int> st;
    for (int i = 0; i < S; ++i) node.insert(X[i]);
    for (int i = 0; i < T; ++i) node.insert(Y[i]);
    set<int, decltype(cmp)> tmp(cmp);
    for (auto it = node.begin(); it != node.end(); ++it) {
        if (it == node.begin()) continue;
        auto k = it;
        --k;
        tmp.insert(lca(*it, *k));
    }
    for (int i: tmp) node.insert(i);
    for (int i: node) {
        if (st.empty()) {
            st.push(i);
            continue;
        }
        if (i == st.top()) continue;
        while (!st.empty() && lca(i, st.top()) != st.top()) st.pop();
        if (!st.empty()) {
            par[i] = st.top();
            newAdj[st.top()].push_back(i);
            st.push(i);
        }
    }
    for (int i: node) if (par[i] == -1) DFS(i, i);
    long long res = ans;
    ans = 1e18;
    for (int i: node) {
        color[i] = 0;
        par[i] = -1;
        dp[i][1] = dp[i][2] = 1e18;
        newAdj[i].clear();
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 24312 KB Output is correct
2 Correct 1046 ms 33648 KB Output is correct
3 Correct 1100 ms 33552 KB Output is correct
4 Correct 1126 ms 33836 KB Output is correct
5 Correct 978 ms 34204 KB Output is correct
6 Correct 530 ms 33540 KB Output is correct
7 Correct 1100 ms 33564 KB Output is correct
8 Correct 1138 ms 33868 KB Output is correct
9 Correct 964 ms 34132 KB Output is correct
10 Correct 535 ms 33480 KB Output is correct
11 Correct 1113 ms 33548 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24032 KB Output is correct
2 Runtime error 614 ms 310904 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 24312 KB Output is correct
2 Correct 1046 ms 33648 KB Output is correct
3 Correct 1100 ms 33552 KB Output is correct
4 Correct 1126 ms 33836 KB Output is correct
5 Correct 978 ms 34204 KB Output is correct
6 Correct 530 ms 33540 KB Output is correct
7 Correct 1100 ms 33564 KB Output is correct
8 Correct 1138 ms 33868 KB Output is correct
9 Correct 964 ms 34132 KB Output is correct
10 Correct 535 ms 33480 KB Output is correct
11 Correct 1113 ms 33548 KB Output is correct
12 Correct 13 ms 24032 KB Output is correct
13 Runtime error 614 ms 310904 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -