oj.uz

Submission #930315

# Submission time Handle Problem Language Result Execution time Memory
930315 2024-02-19T10:45:22 Z cheat_when_I_was_young Factories (JOI14_factories) C++17
100 / 100
 3263 ms 298048 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

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

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[]) {
    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>,
vector<pair<long long, int>>, greater<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] = LLONG_MAX;
    }

    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 = LLONG_MAX;

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

    return ans;
}

Compilation message

factories.cpp: In function 'void build_sparse_table()':
factories.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < tour.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
factories.cpp:38:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int j = 0; j + (1 << i) - 1 < tour.size(); ++j)
      |                         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 1; i < node.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68188 KB Output is correct
2 Correct 938 ms 92920 KB Output is correct
3 Correct 879 ms 92804 KB Output is correct
4 Correct 853 ms 92844 KB Output is correct
5 Correct 832 ms 93160 KB Output is correct
6 Correct 577 ms 92500 KB Output is correct
7 Correct 856 ms 92628 KB Output is correct
8 Correct 878 ms 92756 KB Output is correct
9 Correct 832 ms 92924 KB Output is correct
10 Correct 591 ms 92620 KB Output is correct
11 Correct 889 ms 92868 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 68188 KB Output is correct
2 Correct 1117 ms 263176 KB Output is correct
3 Correct 1059 ms 266428 KB Output is correct
4 Correct 856 ms 263324 KB Output is correct
5 Correct 1134 ms 293448 KB Output is correct
6 Correct 1046 ms 267592 KB Output is correct
7 Correct 949 ms 145900 KB Output is correct
8 Correct 644 ms 144968 KB Output is correct
9 Correct 703 ms 149456 KB Output is correct
10 Correct 919 ms 146304 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 68188 KB Output is correct
2 Correct 938 ms 92920 KB Output is correct
3 Correct 879 ms 92804 KB Output is correct
4 Correct 853 ms 92844 KB Output is correct
5 Correct 832 ms 93160 KB Output is correct
6 Correct 577 ms 92500 KB Output is correct
7 Correct 856 ms 92628 KB Output is correct
8 Correct 878 ms 92756 KB Output is correct
9 Correct 832 ms 92924 KB Output is correct
10 Correct 591 ms 92620 KB Output is correct
11 Correct 889 ms 92868 KB Output is correct
12 Correct 14 ms 68188 KB Output is correct
13 Correct 1117 ms 263176 KB Output is correct
14 Correct 1059 ms 266428 KB Output is correct
15 Correct 856 ms 263324 KB Output is correct
16 Correct 1134 ms 293448 KB Output is correct
17 Correct 1046 ms 267592 KB Output is correct
18 Correct 949 ms 145900 KB Output is correct
19 Correct 644 ms 144968 KB Output is correct
20 Correct 703 ms 149456 KB Output is correct
21 Correct 919 ms 146304 KB Output is correct
22 Correct 2950 ms 277844 KB Output is correct
23 Correct 2248 ms 277700 KB Output is correct
24 Correct 3263 ms 281644 KB Output is correct
25 Correct 2846 ms 283404 KB Output is correct
26 Correct 2168 ms 275400 KB Output is correct
27 Correct 2442 ms 298048 KB Output is correct
28 Correct 1830 ms 274664 KB Output is correct
29 Correct 2083 ms 274528 KB Output is correct
30 Correct 2011 ms 273776 KB Output is correct
31 Correct 1998 ms 273932 KB Output is correct
32 Correct 1219 ms 151768 KB Output is correct
33 Correct 1034 ms 149196 KB Output is correct
34 Correct 1406 ms 145596 KB Output is correct
35 Correct 1317 ms 145840 KB Output is correct
36 Correct 1256 ms 146304 KB Output is correct
37 Correct 1225 ms 145848 KB Output is correct