oj.uz

Submission #735727

# Submission time Handle Problem Language Result Execution time Memory
735727 2023-05-04T13:46:01 Z Jeff12345121 Factories (JOI14_factories) C++14
100 / 100
 6103 ms 178204 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

typedef long long ll;
vector<vector<pair<int,int>>> g;
int n;
const int nmax = 500005,LOG = 21;
int sz[nmax],is_centroid[nmax],depth[nmax],cp[nmax],mput2[4 * nmax];
ll sol[nmax];
int in_reset[nmax];
long long rdis[nmax];

const ll inf = (1LL << 60);

void get_size(int node, int parent) {
    sz[node] = 1;
    for (auto k : g[node]) {
        if (k.first == parent || is_centroid[k.first]) {
            continue;
        }

        get_size(k.first, node);
        sz[node] += sz[k.first];
    }
}
int get_centroid(int node, int parent, int nr_nodes) {
    int half = nr_nodes / 2;
    for (auto k : g[node]) {
        if (k.first == parent || is_centroid[k.first]) {
            continue;
        }


        if (sz[k.first] > half) {
            return get_centroid(k.first, node, nr_nodes);
        }
    }
    return node;
}
void build_centroid(int node, int centroid_parent) {
    get_size(node, 0);
    int centroid = get_centroid(node,0, sz[node]);

    cp[centroid] = centroid_parent;
    is_centroid[centroid] = 1;
    for (auto k : g[centroid]) {
        if (is_centroid[k.first] == 0) {
            build_centroid(k.first , centroid);
        }
    }
}


vector<int> euler;
int tin[nmax],tout[nmax],cnt = 0;
void get_depth(int node, int parent) {
    for (auto k : g[node]) {
        if (k.first == parent) {
            continue;
        }

        depth[k.first] = depth[node] + 1; 
        rdis[k.first] = rdis[node] + k.second;
        get_depth(k.first, node);
    }
}
void get_euler(int node, int parent) {
    tin[node] = euler.size();
    euler.push_back(node);
    for (auto k : g[node]) {
        if (k.first == parent) {
            continue;
        }
        get_euler(k.first , node);
        euler.push_back(node);
    }
}

struct Wow {
    int node;
    bool operator < (const Wow &other) const {
        return depth[node] < depth[other.node];
    }
};
Wow rmq[LOG][4 * nmax];
void build_rmq() {
    for (int i = 1; i < euler.size(); i++) {
        rmq[0][i].node = euler[i];
    }

    mput2[1] = 0;
    for (int i = 2; i <= 2 * n; i++) {
        mput2[i] = mput2[i / 2] + 1;
    }

    for (int lvl = 1; lvl < LOG; lvl++) {
        for (int i = 1; i < (int)euler.size() - (1 << lvl) + 1; i++) {
            rmq[lvl][i] = min(rmq[lvl-1][i] , rmq[lvl - 1][i + (1 << (lvl-1))]);
        }
    }
}
int query_rmq(int l, int r) {
    if (l > r) {
        swap(l,r);
    }

    int put = mput2[r - l + 1];

    return min(rmq[put][l], rmq[put][r - (1 << put) + 1]).node;
}
int get_lca(int u, int v) {
    return query_rmq(tin[u],tin[v]);
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    g.resize(n + 1);
    for (int i = 1; i < n; i++) {
        A[i - 1]++;
        B[i - 1]++;
        g[A[i - 1]].push_back({B[i - 1] , D[i - 1]});
        g[B[i - 1]].push_back({A[i - 1], D[i - 1]});
    }

    for (int i = 1; i <= n; i++) {
        sol[i] = inf;
    }
    
    get_depth(1,0);
    euler.push_back(-1);
    get_euler(1, 0);
    build_rmq();
    build_centroid(1, 0);
    return;
}


ll get_dis(int u, int v) {
    int lca = get_lca(u,v);
    return rdis[u] + rdis[v] - 2 * rdis[lca];
}
long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S;i++) {
        X[i]++;
    }
    for (int i = 0; i < T;i++){
        Y[i]++;
    }

    queue<int> reset_nodes;
    
    for (int i = 1; i <= S; i++) {
        for (int node = X[i - 1]; node != 0; node = cp[node]) {
            sol[node] = min(sol[node] , get_dis(node, X[i - 1]));
            if (!in_reset[node]) {
                in_reset[node] = 1;
                reset_nodes.push(node);
            }
        }
    }

    ll res = inf;
    for (int i = 1; i <= T; i++) {
        for (int node = Y[i - 1]; node != 0; node = cp[node]) {
            res = min(res, sol[node] + get_dis(node, Y[i - 1]));
        }
    }

    while(!reset_nodes.empty()) {
        in_reset[reset_nodes.front()] = 0;
        sol[reset_nodes.front()] = inf;
        reset_nodes.pop();
    }
    return res;
}

Compilation message

factories.cpp: In function 'void build_rmq()':
factories.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 1; i < euler.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 972 KB Output is correct
2 Correct 341 ms 17040 KB Output is correct
3 Correct 442 ms 19156 KB Output is correct
4 Correct 418 ms 19152 KB Output is correct
5 Correct 442 ms 19404 KB Output is correct
6 Correct 202 ms 19148 KB Output is correct
7 Correct 428 ms 19088 KB Output is correct
8 Correct 440 ms 19156 KB Output is correct
9 Correct 487 ms 19332 KB Output is correct
10 Correct 196 ms 19024 KB Output is correct
11 Correct 439 ms 19108 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2553 ms 164056 KB Output is correct
3 Correct 3492 ms 165628 KB Output is correct
4 Correct 810 ms 148516 KB Output is correct
5 Correct 4778 ms 178204 KB Output is correct
6 Correct 3542 ms 150908 KB Output is correct
7 Correct 1695 ms 50100 KB Output is correct
8 Correct 375 ms 50872 KB Output is correct
9 Correct 1995 ms 54452 KB Output is correct
10 Correct 2043 ms 51804 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 972 KB Output is correct
2 Correct 341 ms 17040 KB Output is correct
3 Correct 442 ms 19156 KB Output is correct
4 Correct 418 ms 19152 KB Output is correct
5 Correct 442 ms 19404 KB Output is correct
6 Correct 202 ms 19148 KB Output is correct
7 Correct 428 ms 19088 KB Output is correct
8 Correct 440 ms 19156 KB Output is correct
9 Correct 487 ms 19332 KB Output is correct
10 Correct 196 ms 19024 KB Output is correct
11 Correct 439 ms 19108 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2553 ms 164056 KB Output is correct
14 Correct 3492 ms 165628 KB Output is correct
15 Correct 810 ms 148516 KB Output is correct
16 Correct 4778 ms 178204 KB Output is correct
17 Correct 3542 ms 150908 KB Output is correct
18 Correct 1695 ms 50100 KB Output is correct
19 Correct 375 ms 50872 KB Output is correct
20 Correct 1995 ms 54452 KB Output is correct
21 Correct 2043 ms 51804 KB Output is correct
22 Correct 3276 ms 149284 KB Output is correct
23 Correct 3436 ms 151892 KB Output is correct
24 Correct 4911 ms 152144 KB Output is correct
25 Correct 5102 ms 155340 KB Output is correct
26 Correct 4903 ms 151796 KB Output is correct
27 Correct 6103 ms 175604 KB Output is correct
28 Correct 1102 ms 152084 KB Output is correct
29 Correct 4841 ms 151424 KB Output is correct
30 Correct 5002 ms 150732 KB Output is correct
31 Correct 4932 ms 151716 KB Output is correct
32 Correct 1634 ms 55688 KB Output is correct
33 Correct 378 ms 51416 KB Output is correct
34 Correct 1101 ms 47940 KB Output is correct
35 Correct 1112 ms 47924 KB Output is correct
36 Correct 1488 ms 48580 KB Output is correct
37 Correct 1525 ms 48728 KB Output is correct