oj.uz

Submission #780235

# Submission time Handle Problem Language Result Execution time Memory
780235 2023-07-12T07:33:38 Z cheat_when_I_was_young Factories (JOI14_factories) C++17
100 / 100
 5029 ms 281412 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int NM = 5e5 + 5;
const int LG = __lg(NM<<1) + 1;
int in[NM], h[NM], color[NM], par[NM];
long long d[NM], dp[NM][3], ans;
pair<int,int> ST[LG][NM<<1];
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), tmp(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]);
    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;
        }
        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 34 ms 24276 KB Output is correct
2 Correct 1020 ms 33792 KB Output is correct
3 Correct 1111 ms 33532 KB Output is correct
4 Correct 1124 ms 33852 KB Output is correct
5 Correct 975 ms 34128 KB Output is correct
6 Correct 613 ms 33492 KB Output is correct
7 Correct 1092 ms 33664 KB Output is correct
8 Correct 1127 ms 33848 KB Output is correct
9 Correct 1014 ms 34124 KB Output is correct
10 Correct 598 ms 33532 KB Output is correct
11 Correct 1178 ms 33560 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24040 KB Output is correct
2 Correct 1460 ms 231108 KB Output is correct
3 Correct 1621 ms 234920 KB Output is correct
4 Correct 904 ms 231968 KB Output is correct
5 Correct 1446 ms 274520 KB Output is correct
6 Correct 1729 ms 236212 KB Output is correct
7 Correct 1776 ms 71608 KB Output is correct
8 Correct 900 ms 71828 KB Output is correct
9 Correct 1067 ms 78504 KB Output is correct
10 Correct 1740 ms 72852 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24276 KB Output is correct
2 Correct 1020 ms 33792 KB Output is correct
3 Correct 1111 ms 33532 KB Output is correct
4 Correct 1124 ms 33852 KB Output is correct
5 Correct 975 ms 34128 KB Output is correct
6 Correct 613 ms 33492 KB Output is correct
7 Correct 1092 ms 33664 KB Output is correct
8 Correct 1127 ms 33848 KB Output is correct
9 Correct 1014 ms 34124 KB Output is correct
10 Correct 598 ms 33532 KB Output is correct
11 Correct 1178 ms 33560 KB Output is correct
12 Correct 18 ms 24040 KB Output is correct
13 Correct 1460 ms 231108 KB Output is correct
14 Correct 1621 ms 234920 KB Output is correct
15 Correct 904 ms 231968 KB Output is correct
16 Correct 1446 ms 274520 KB Output is correct
17 Correct 1729 ms 236212 KB Output is correct
18 Correct 1776 ms 71608 KB Output is correct
19 Correct 900 ms 71828 KB Output is correct
20 Correct 1067 ms 78504 KB Output is correct
21 Correct 1740 ms 72852 KB Output is correct
22 Correct 5029 ms 244388 KB Output is correct
23 Correct 3435 ms 247028 KB Output is correct
24 Correct 4996 ms 252564 KB Output is correct
25 Correct 4575 ms 256024 KB Output is correct
26 Correct 3747 ms 239068 KB Output is correct
27 Correct 3302 ms 281412 KB Output is correct
28 Correct 2248 ms 241052 KB Output is correct
29 Correct 3239 ms 237620 KB Output is correct
30 Correct 3193 ms 236784 KB Output is correct
31 Correct 3127 ms 237520 KB Output is correct
32 Correct 1849 ms 87364 KB Output is correct
33 Correct 1162 ms 76628 KB Output is correct
34 Correct 1941 ms 70424 KB Output is correct
35 Correct 1772 ms 70060 KB Output is correct
36 Correct 2069 ms 71112 KB Output is correct
37 Correct 2036 ms 70992 KB Output is correct