oj.uz

Submission #735637

# Submission time Handle Problem Language Result Execution time Memory
735637 2023-05-04T12:23:49 Z Jeff12345121 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 176364 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 = 20;
int sz[nmax],is_centroid[nmax],lift[LOG][nmax],depth[nmax],cp[nmax];
ll sol[nmax];
int in_reset[nmax];
long long dis[LOG][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);
        }
    }
}


void find_parents(int node) {
    for (auto k : g[node]) {
        if (k.first == lift[0][node]) {
            continue;
        }

        lift[0][k.first] = node;
        dis[0][k.first] = k.second;
        depth[k.first] = depth[node] + 1;
        find_parents(k.first);
    }
}
void get_lift() {
    find_parents(1);

    for (int lvl = 1; lvl < LOG; lvl++) {
        for (int i = 1; i <= n; i++) {
            lift[lvl][i] = lift[lvl - 1][lift[lvl - 1][i]];
            dis[lvl][i] = dis[lvl-1][lift[lvl-1][i]] + dis[lvl-1][i];
        }
    }
}
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_lift();
    build_centroid(1, 0);
    return;
}


ll get_dis(int u, int v) {
    if (u == v) {
        return 0LL;
    }

    if (depth[u] < depth[v]) {
        swap(u,v);
    }

    ll cost = 0;
    for (int lvl = LOG - 1; lvl >= 0 && depth[u] > depth[v]; lvl--) {
        if (depth[lift[lvl][u]] >= depth[v]) {
            cost += dis[lvl][u];
            u = lift[lvl][u];
        }
    }

    if (u == v) {
        return cost;
    }

    for (int lvl = LOG - 1; lvl >= 0; lvl--) {
        if (lift[lvl][u] != lift[lvl][v]) {
            cost += dis[lvl][u];
            u = lift[lvl][u];
            cost += dis[lvl][v];
            v = lift[lvl][v];
        }
    }

    cost += dis[0][u];
    cost += dis[0][v];
    return cost;
}
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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1128 KB Output is correct
2 Correct 1000 ms 10396 KB Output is correct
3 Correct 1956 ms 19828 KB Output is correct
4 Correct 1988 ms 19768 KB Output is correct
5 Correct 2482 ms 20072 KB Output is correct
6 Correct 344 ms 19732 KB Output is correct
7 Correct 2021 ms 19884 KB Output is correct
8 Correct 2467 ms 19892 KB Output is correct
9 Correct 2687 ms 20284 KB Output is correct
10 Correct 373 ms 19744 KB Output is correct
11 Correct 1866 ms 19820 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 4572 ms 174732 KB Output is correct
3 Execution timed out 8073 ms 176364 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1128 KB Output is correct
2 Correct 1000 ms 10396 KB Output is correct
3 Correct 1956 ms 19828 KB Output is correct
4 Correct 1988 ms 19768 KB Output is correct
5 Correct 2482 ms 20072 KB Output is correct
6 Correct 344 ms 19732 KB Output is correct
7 Correct 2021 ms 19884 KB Output is correct
8 Correct 2467 ms 19892 KB Output is correct
9 Correct 2687 ms 20284 KB Output is correct
10 Correct 373 ms 19744 KB Output is correct
11 Correct 1866 ms 19820 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 4572 ms 174732 KB Output is correct
14 Execution timed out 8073 ms 176364 KB Time limit exceeded
15 Halted 0 ms 0 KB -