oj.uz

Submission #780238

# Submission time Handle Problem Language Result Execution time Memory
780238 2023-07-12T07:35:14 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 4487 ms 281152 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 33 ms 24400 KB Output is correct
2 Correct 1036 ms 34176 KB Output is correct
3 Correct 1106 ms 34156 KB Output is correct
4 Correct 1120 ms 34368 KB Output is correct
5 Correct 982 ms 34628 KB Output is correct
6 Correct 539 ms 34132 KB Output is correct
7 Correct 1120 ms 34048 KB Output is correct
8 Correct 1129 ms 34504 KB Output is correct
9 Correct 966 ms 34780 KB Output is correct
10 Correct 546 ms 34156 KB Output is correct
11 Correct 1128 ms 34176 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24020 KB Output is correct
2 Correct 1281 ms 231088 KB Output is correct
3 Correct 1506 ms 234936 KB Output is correct
4 Correct 866 ms 231944 KB Output is correct
5 Correct 1233 ms 274508 KB Output is correct
6 Correct 1501 ms 236272 KB Output is correct
7 Correct 1454 ms 70836 KB Output is correct
8 Correct 765 ms 71172 KB Output is correct
9 Correct 1030 ms 77716 KB Output is correct
10 Correct 1533 ms 72128 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24400 KB Output is correct
2 Correct 1036 ms 34176 KB Output is correct
3 Correct 1106 ms 34156 KB Output is correct
4 Correct 1120 ms 34368 KB Output is correct
5 Correct 982 ms 34628 KB Output is correct
6 Correct 539 ms 34132 KB Output is correct
7 Correct 1120 ms 34048 KB Output is correct
8 Correct 1129 ms 34504 KB Output is correct
9 Correct 966 ms 34780 KB Output is correct
10 Correct 546 ms 34156 KB Output is correct
11 Correct 1128 ms 34176 KB Output is correct
12 Correct 15 ms 24020 KB Output is correct
13 Correct 1281 ms 231088 KB Output is correct
14 Correct 1506 ms 234936 KB Output is correct
15 Correct 866 ms 231944 KB Output is correct
16 Correct 1233 ms 274508 KB Output is correct
17 Correct 1501 ms 236272 KB Output is correct
18 Correct 1454 ms 70836 KB Output is correct
19 Correct 765 ms 71172 KB Output is correct
20 Correct 1030 ms 77716 KB Output is correct
21 Correct 1533 ms 72128 KB Output is correct
22 Correct 4086 ms 244424 KB Output is correct
23 Correct 3067 ms 246688 KB Output is correct
24 Correct 4487 ms 252528 KB Output is correct
25 Correct 4043 ms 256068 KB Output is correct
26 Correct 3232 ms 239012 KB Output is correct
27 Correct 3129 ms 281152 KB Output is correct
28 Correct 1995 ms 240580 KB Output is correct
29 Correct 3032 ms 237520 KB Output is correct
30 Correct 3097 ms 236712 KB Output is correct
31 Correct 2966 ms 237432 KB Output is correct
32 Correct 1788 ms 86904 KB Output is correct
33 Correct 1141 ms 76108 KB Output is correct
34 Correct 1806 ms 69748 KB Output is correct
35 Correct 1715 ms 69608 KB Output is correct
36 Correct 1939 ms 70684 KB Output is correct
37 Correct 1875 ms 70548 KB Output is correct