oj.uz

Submission #930323

# Submission time Handle Problem Language Result Execution time Memory
930323 2024-02-19T10:55:23 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 3218 ms 275128 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 30 ms 68184 KB Output is correct
2 Correct 920 ms 88060 KB Output is correct
3 Correct 879 ms 88000 KB Output is correct
4 Correct 859 ms 88232 KB Output is correct
5 Correct 826 ms 88172 KB Output is correct
6 Correct 578 ms 88004 KB Output is correct
7 Correct 862 ms 88048 KB Output is correct
8 Correct 882 ms 88112 KB Output is correct
9 Correct 858 ms 88296 KB Output is correct
10 Correct 574 ms 88012 KB Output is correct
11 Correct 858 ms 88128 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 68188 KB Output is correct
2 Correct 1179 ms 253968 KB Output is correct
3 Correct 1096 ms 257728 KB Output is correct
4 Correct 867 ms 254588 KB Output is correct
5 Correct 1162 ms 275128 KB Output is correct
6 Correct 1164 ms 249064 KB Output is correct
7 Correct 920 ms 131956 KB Output is correct
8 Correct 674 ms 131000 KB Output is correct
9 Correct 670 ms 135368 KB Output is correct
10 Correct 839 ms 132144 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 68184 KB Output is correct
2 Correct 920 ms 88060 KB Output is correct
3 Correct 879 ms 88000 KB Output is correct
4 Correct 859 ms 88232 KB Output is correct
5 Correct 826 ms 88172 KB Output is correct
6 Correct 578 ms 88004 KB Output is correct
7 Correct 862 ms 88048 KB Output is correct
8 Correct 882 ms 88112 KB Output is correct
9 Correct 858 ms 88296 KB Output is correct
10 Correct 574 ms 88012 KB Output is correct
11 Correct 858 ms 88128 KB Output is correct
12 Correct 13 ms 68188 KB Output is correct
13 Correct 1179 ms 253968 KB Output is correct
14 Correct 1096 ms 257728 KB Output is correct
15 Correct 867 ms 254588 KB Output is correct
16 Correct 1162 ms 275128 KB Output is correct
17 Correct 1164 ms 249064 KB Output is correct
18 Correct 920 ms 131956 KB Output is correct
19 Correct 674 ms 131000 KB Output is correct
20 Correct 670 ms 135368 KB Output is correct
21 Correct 839 ms 132144 KB Output is correct
22 Correct 3121 ms 253660 KB Output is correct
23 Correct 2299 ms 253012 KB Output is correct
24 Correct 3218 ms 257644 KB Output is correct
25 Correct 2777 ms 258904 KB Output is correct
26 Correct 2202 ms 251068 KB Output is correct
27 Correct 2611 ms 273744 KB Output is correct
28 Correct 1860 ms 250488 KB Output is correct
29 Correct 2021 ms 250720 KB Output is correct
30 Correct 1978 ms 250256 KB Output is correct
31 Correct 2075 ms 250496 KB Output is correct
32 Correct 1319 ms 138072 KB Output is correct
33 Correct 874 ms 135184 KB Output is correct
34 Correct 1332 ms 132028 KB Output is correct
35 Correct 1320 ms 131720 KB Output is correct
36 Correct 1297 ms 132372 KB Output is correct
37 Correct 1325 ms 132708 KB Output is correct