oj.uz

Submission #780194

# Submission time Handle Problem Language Result Execution time Memory
780194 2023-07-12T07:11:56 Z cheat_when_I_was_young Factories (JOI14_factories) C++17
0 / 100
 8000 ms 310960 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;
    }
}

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

void DFS(int u, int par) {
    for (int &v: newAdj[u]) {
        if (v == par || v == u) continue;
        DFS(v, u);
    }
    if (color[u]) dp[u][color[u]] = 0;
    for (int &v: newAdj[u]) {
        if (v == par || v == u) 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]);
}

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;
    }
    vector<int> node;
    stack<int> st;
    for (int i = 0; i < S; ++i) node.push_back(X[i]);
    for (int i = 0; i < T; ++i) node.push_back(Y[i]);
    sort(node.begin(), node.end(), cmp);
    int N = node.size();
    for (int i = 1; i < N; ++i) node.push_back(lca(node[i], node[i-1]));
    sort(node.begin(), node.end(), cmp);
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24276 KB Output is correct
2 Correct 776 ms 33616 KB Output is correct
3 Correct 743 ms 33608 KB Output is correct
4 Correct 783 ms 33616 KB Output is correct
5 Correct 699 ms 33928 KB Output is correct
6 Execution timed out 8035 ms 33452 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24136 KB Output is correct
2 Runtime error 617 ms 310960 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 31 ms 24276 KB Output is correct
2 Correct 776 ms 33616 KB Output is correct
3 Correct 743 ms 33608 KB Output is correct
4 Correct 783 ms 33616 KB Output is correct
5 Correct 699 ms 33928 KB Output is correct
6 Execution timed out 8035 ms 33452 KB Time limit exceeded
7 Halted 0 ms 0 KB -