Submission #930296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930296	2024-02-19T10:13:37 Z	cheat_when_I_was_young	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KB

factories

const int NM = 5e5 + 5;
const int LG = __lg(NM);

int n;
vector<pair<int, int>> adj[NM];
bool visited[NM];
vector<int> tour;
int depth[NM], tin[NM], tout[NM];
long long dist[NM];
pair<int, int> ST[LG + 2][NM << 1];

void dfs_euler_tour(const int &u) {
    visited[u] = 1;

    tin[u] = tour.size();
    tour.emplace_back(u);

    for (auto &[v, w]: adj[u])
        if (!visited[v]) {
            depth[v] = depth[u] + 1;
            dist[v] = dist[u] + w;

            dfs_euler_tour(v);
            tour.emplace_back(u);
        }

    tout[u] = tour.size() - 1;
}

void build_sparse_table() {
    for (int i = 0; i < tour.size(); ++i)
        ST[0][i] = {depth[tour[i]], tour[i]};

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

int lca(const int &u, const int &v) {
    int l = tin[u], r = tin[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[]) {
    n = N;

    for (int i = 0; i < n - 1; ++i) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }

    dfs_euler_tour(0);
    build_sparse_table();
}

bool cmp(const int &u, const int &v) {
    return tin[u] < tin[v];
}

bool is_anc(const int &u, const int &v) {
    return tin[u] <= tin[v] && tin[v] <= tout[u];
}

vector<pair<int, long long>> new_adj[NM];
priority_queue<pair<long long, int>> q;
long long d[NM];

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> node;

    for (int i = 0; i < S; ++i)
        node.emplace_back(X[i]);

    for (int i = 0; i < T; ++i)
        node.emplace_back(Y[i]);

    sort(node.begin(), node.end(), cmp);
    node.erase(unique(node.begin(), node.end()), node.end());

    int tmp = node.size();

    for (int i = 0; i + 1 < tmp; ++i)
        node.emplace_back(lca(node[i], node[i + 1]));

    sort(node.begin(), node.end(), cmp);
    node.erase(unique(node.begin(), node.end()), node.end());

    for (auto &i: node) {
        new_adj[i].clear();
        visited[i] = 0;
        d[i] = 1e18;
    }

    for (int i = 0; i < S; ++i) {
        d[X[i]] = 0;
        q.push({0, X[i]});
    }

    stack<int> st;
    st.push(node[0]);

    for (int i = 1; i < node.size(); ++i) {
        while (!is_anc(st.top(), node[i]))
            st.pop();

        new_adj[st.top()].emplace_back(node[i], dist[node[i]] - dist[st.top()]);
        new_adj[node[i]].emplace_back(st.top(), dist[node[i]] - dist[st.top()]);

        st.push(node[i]);
    }

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (visited[u]) continue;
        visited[u] = 1;

        for (auto &[v, w]: new_adj[u])
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
    }

    long long ans = 1e18;

    for (int i = 0; i < T; ++i)
        ans = min(ans, d[Y[i]]);

    return ans;
}

Compilation message

factories.cpp:2:16: error: '__lg' was not declared in this scope
    2 | const int LG = __lg(NM);
      |                ^~~~
factories.cpp:5:1: error: 'vector' does not name a type
    5 | vector<pair<int, int>> adj[NM];
      | ^~~~~~
factories.cpp:7:1: error: 'vector' does not name a type
    7 | vector<int> tour;
      | ^~~~~~
factories.cpp:10:1: error: 'pair' does not name a type
   10 | pair<int, int> ST[LG + 2][NM << 1];
      | ^~~~
factories.cpp: In function 'void dfs_euler_tour(const int&)':
factories.cpp:15:14: error: 'tour' was not declared in this scope; did you mean 'tout'?
   15 |     tin[u] = tour.size();
      |              ^~~~
      |              tout
factories.cpp:18:24: error: 'adj' was not declared in this scope
   18 |     for (auto &[v, w]: adj[u])
      |                        ^~~
factories.cpp: In function 'void build_sparse_table()':
factories.cpp:31:25: error: 'tour' was not declared in this scope; did you mean 'tout'?
   31 |     for (int i = 0; i < tour.size(); ++i)
      |                         ^~~~
      |                         tout
factories.cpp:32:9: error: 'ST' was not declared in this scope
   32 |         ST[0][i] = {depth[tour[i]], tour[i]};
      |         ^~
factories.cpp:35:44: error: 'tour' was not declared in this scope; did you mean 'tout'?
   35 |         for (int j = 0; j + (1 << i) - 1 < tour.size(); ++j)
      |                                            ^~~~
      |                                            tout
factories.cpp:36:13: error: 'ST' was not declared in this scope
   36 |             ST[i][j] = min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
      |             ^~
factories.cpp:36:24: error: 'min' was not declared in this scope; did you mean 'tin'?
   36 |             ST[i][j] = min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
      |                        ^~~
      |                        tin
factories.cpp: In function 'int lca(const int&, const int&)':
factories.cpp:41:16: error: 'swap' was not declared in this scope
   41 |     if (l > r) swap(l, r);
      |                ^~~~
factories.cpp:43:13: error: '__lg' was not declared in this scope
   43 |     int k = __lg(r - l + 1);
      |             ^~~~
factories.cpp:44:16: error: 'ST' was not declared in this scope
   44 |     return min(ST[k][l], ST[k][r - (1 << k) + 1]).second;
      |                ^~
factories.cpp:44:12: error: 'min' was not declared in this scope; did you mean 'tin'?
   44 |     return min(ST[k][l], ST[k][r - (1 << k) + 1]).second;
      |            ^~~
      |            tin
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:51:9: error: 'adj' was not declared in this scope
   51 |         adj[A[i]].emplace_back(B[i], D[i]);
      |         ^~~
factories.cpp: At global scope:
factories.cpp:67:1: error: 'vector' does not name a type
   67 | vector<pair<int, long long>> new_adj[NM];
      | ^~~~~~
factories.cpp:68:1: error: 'priority_queue' does not name a type
   68 | priority_queue<pair<long long, int>> q;
      | ^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:72:5: error: 'vector' was not declared in this scope
   72 |     vector<int> node;
      |     ^~~~~~
factories.cpp:72:12: error: expected primary-expression before 'int'
   72 |     vector<int> node;
      |            ^~~
factories.cpp:75:9: error: 'node' was not declared in this scope
   75 |         node.emplace_back(X[i]);
      |         ^~~~
factories.cpp:78:9: error: 'node' was not declared in this scope
   78 |         node.emplace_back(Y[i]);
      |         ^~~~
factories.cpp:80:10: error: 'node' was not declared in this scope
   80 |     sort(node.begin(), node.end(), cmp);
      |          ^~~~
factories.cpp:80:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   80 |     sort(node.begin(), node.end(), cmp);
      |     ^~~~
      |     short
factories.cpp:81:16: error: 'unique' was not declared in this scope
   81 |     node.erase(unique(node.begin(), node.end()), node.end());
      |                ^~~~~~
factories.cpp:92:9: error: 'new_adj' was not declared in this scope
   92 |         new_adj[i].clear();
      |         ^~~~~~~
factories.cpp:99:9: error: 'q' was not declared in this scope
   99 |         q.push({0, X[i]});
      |         ^
factories.cpp:102:5: error: 'stack' was not declared in this scope
  102 |     stack<int> st;
      |     ^~~~~
factories.cpp:102:11: error: expected primary-expression before 'int'
  102 |     stack<int> st;
      |           ^~~
factories.cpp:103:5: error: 'st' was not declared in this scope; did you mean 'std'?
  103 |     st.push(node[0]);
      |     ^~
      |     std
factories.cpp:109:9: error: 'new_adj' was not declared in this scope
  109 |         new_adj[st.top()].emplace_back(node[i], dist[node[i]] - dist[st.top()]);
      |         ^~~~~~~
factories.cpp:115:13: error: 'q' was not declared in this scope
  115 |     while (!q.empty()) {
      |             ^
factories.cpp:122:28: error: 'new_adj' was not declared in this scope
  122 |         for (auto &[v, w]: new_adj[u])
      |                            ^~~~~~~
factories.cpp:132:15: error: 'min' was not declared in this scope; did you mean 'tin'?
  132 |         ans = min(ans, d[Y[i]]);
      |               ^~~
      |               tin