oj.uz

Submission #780226

# Submission time Handle Problem Language Result Execution time Memory
780226 2023-07-12T07:26:14 Z cheat_when_I_was_young Factories (JOI14_factories) C++17
15 / 100
 1189 ms 310956 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));
    }
    if (tmp.size()) 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 33 ms 24328 KB Output is correct
2 Correct 1102 ms 33672 KB Output is correct
3 Correct 1140 ms 33524 KB Output is correct
4 Correct 1144 ms 33864 KB Output is correct
5 Correct 1039 ms 34128 KB Output is correct
6 Correct 584 ms 33528 KB Output is correct
7 Correct 1189 ms 33524 KB Output is correct
8 Correct 1161 ms 33852 KB Output is correct
9 Correct 1042 ms 34136 KB Output is correct
10 Correct 567 ms 33520 KB Output is correct
11 Correct 1138 ms 33556 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24148 KB Output is correct
2 Runtime error 836 ms 310956 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 33 ms 24328 KB Output is correct
2 Correct 1102 ms 33672 KB Output is correct
3 Correct 1140 ms 33524 KB Output is correct
4 Correct 1144 ms 33864 KB Output is correct
5 Correct 1039 ms 34128 KB Output is correct
6 Correct 584 ms 33528 KB Output is correct
7 Correct 1189 ms 33524 KB Output is correct
8 Correct 1161 ms 33852 KB Output is correct
9 Correct 1042 ms 34136 KB Output is correct
10 Correct 567 ms 33520 KB Output is correct
11 Correct 1138 ms 33556 KB Output is correct
12 Correct 16 ms 24148 KB Output is correct
13 Runtime error 836 ms 310956 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -