oj.uz

Submission #768080

# Submission time Handle Problem Language Result Execution time Memory
768080 2023-06-27T12:33:40 Z faruk Factories (JOI14_factories) C++17
100 / 100
 5424 ms 474676 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int K = 20;
struct rmq {
    int n;
    vector<int> lg;
    vector<vector<pii> > table;

    rmq() {}
    rmq(vector<pii> arr) {
        n = arr.size();
        lg.resize(n + 1);
        for (int i = 2; i <= n; i++)
            lg[i] = lg[i / 2] + 1;
        table.resize(K, vector<pii>(n));
        table[0] = arr;
        for (int i = 1; i < K; i++)
            for (int j = 0; j + (1 << i) <= n; j++)
                table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);    
    }

    pii query(int l, int r) {
        int siz = lg[r - l + 1];
        return min(table[siz][l], table[siz][r - (1 << siz) + 1]);
    }
};

int n;
vector<vector<pii> > graph;
vector<int> beg;
vector<int> endd;
vector<pii> euler_tour;
vector<ll> dist_to_1;
rmq lca_rmq;
void dfs_lca(int curr, int par, ll height, ll dt1) {
    beg[curr] = euler_tour.size();
    dist_to_1[curr] = dt1;
    euler_tour.push_back({height, curr});

    for (pii a : graph[curr]) {
        if (a.first == par)
            continue;
        dfs_lca(a.first, curr, height + 1, dt1 + a.second);
        euler_tour.push_back({height, curr});
    }
    endd[curr] = euler_tour.size() - 1;
}

void init_lca() {
    beg = vector<int>(n + 1);
    endd = vector<int>(n + 1);
    dist_to_1 = vector<ll>(n + 1);
    dfs_lca(0, -1, 0, 0);
    lca_rmq = rmq(euler_tour);
}

int lca(int a, int b) {
    if (beg[a] > beg[b])
        swap(a, b);
    return lca_rmq.query(beg[a], endd[b]).second;
}

ll dist(int a, int b) {
    if (a == b)
        return 0;
    return dist_to_1[a] + dist_to_1[b] - 2LL*dist_to_1[lca(a, b)];
}

// centroid init
vector<int> centroid_par;
vector<bool> vis;
vector<int> sz;

int get_siz(int curr, int par) {
    sz[curr] = 1;
    for (auto &[a, d] : graph[curr]) 
        if (!vis[a] and a != par)
            sz[curr] += get_siz(a, curr);
    return sz[curr];
}

int get_centroid(int curr, int par, int subtree_size) {
    for (auto &[a, d] : graph[curr])
        if (!vis[a] and a != par and 2LL * sz[a] > subtree_size)
            return get_centroid(a, curr, subtree_size);
    return curr;
}

void centroid_init(int curr, int c_par) {
    int my_siz = get_siz(curr, -1);
    int centroid = get_centroid(curr, -1, my_siz);
    vis[centroid] = 1;
    centroid_par[centroid] = c_par;
    for (auto &[a, d] : graph[centroid])
        if (!vis[a])
            centroid_init(a, centroid);
}

void centroid_full_init() {
    centroid_par = vector<int>(n+1);
    vis = vector<bool>(n+1);
    sz = vector<int>(n+1);
    centroid_init(0, -1);
}

vector<ll> best;
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    graph = vector<vector<pii> >(N+1);
    for (int i = 0; i < n - 1; i++)
    {
        graph[A[i]].push_back({B[i], D[i]});
        graph[B[i]].push_back({A[i], D[i]});
    }
    init_lca();
    centroid_full_init();
    best = vector<ll>(n+1,1e18);
}

vector<int> changed;
void change_col(int curr, int og) {
    if (curr == -1)
        return;
    if (best[curr] > dist(curr, og))
        changed.push_back(curr);
    best[curr] = min(best[curr], dist(curr, og));
    change_col(centroid_par[curr], og);
}

ll query(int curr, int og) {
    if (curr == -1)
        return 1e18;
    return min(best[curr] + dist(curr, og), query(centroid_par[curr], og));
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++)
        change_col(X[i], X[i]);
    ll out = 1e18;
    for (int i = 0; i < T; i++)
        out = min(out, query(Y[i], Y[i]));
    for (int a : changed)
        best[a] = 1e18;
    changed.clear();
    return out;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 996 KB Output is correct
2 Correct 401 ms 16760 KB Output is correct
3 Correct 559 ms 16772 KB Output is correct
4 Correct 525 ms 16780 KB Output is correct
5 Correct 508 ms 17260 KB Output is correct
6 Correct 171 ms 16716 KB Output is correct
7 Correct 550 ms 16868 KB Output is correct
8 Correct 596 ms 21960 KB Output is correct
9 Correct 497 ms 20052 KB Output is correct
10 Correct 178 ms 21856 KB Output is correct
11 Correct 542 ms 22000 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 2525 ms 421156 KB Output is correct
3 Correct 3521 ms 427856 KB Output is correct
4 Correct 821 ms 423708 KB Output is correct
5 Correct 4062 ms 474676 KB Output is correct
6 Correct 3620 ms 427240 KB Output is correct
7 Correct 1937 ms 96676 KB Output is correct
8 Correct 349 ms 95284 KB Output is correct
9 Correct 1402 ms 101416 KB Output is correct
10 Correct 1917 ms 96956 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 996 KB Output is correct
2 Correct 401 ms 16760 KB Output is correct
3 Correct 559 ms 16772 KB Output is correct
4 Correct 525 ms 16780 KB Output is correct
5 Correct 508 ms 17260 KB Output is correct
6 Correct 171 ms 16716 KB Output is correct
7 Correct 550 ms 16868 KB Output is correct
8 Correct 596 ms 21960 KB Output is correct
9 Correct 497 ms 20052 KB Output is correct
10 Correct 178 ms 21856 KB Output is correct
11 Correct 542 ms 22000 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 2525 ms 421156 KB Output is correct
14 Correct 3521 ms 427856 KB Output is correct
15 Correct 821 ms 423708 KB Output is correct
16 Correct 4062 ms 474676 KB Output is correct
17 Correct 3620 ms 427240 KB Output is correct
18 Correct 1937 ms 96676 KB Output is correct
19 Correct 349 ms 95284 KB Output is correct
20 Correct 1402 ms 101416 KB Output is correct
21 Correct 1917 ms 96956 KB Output is correct
22 Correct 3784 ms 427400 KB Output is correct
23 Correct 3775 ms 428160 KB Output is correct
24 Correct 4917 ms 433056 KB Output is correct
25 Correct 4920 ms 434640 KB Output is correct
26 Correct 5343 ms 433416 KB Output is correct
27 Correct 5424 ms 464944 KB Output is correct
28 Correct 1083 ms 425528 KB Output is correct
29 Correct 5194 ms 432784 KB Output is correct
30 Correct 5157 ms 439560 KB Output is correct
31 Correct 5390 ms 432880 KB Output is correct
32 Correct 1496 ms 102284 KB Output is correct
33 Correct 330 ms 95308 KB Output is correct
34 Correct 1736 ms 94868 KB Output is correct
35 Correct 1607 ms 94968 KB Output is correct
36 Correct 1915 ms 96188 KB Output is correct
37 Correct 1883 ms 96140 KB Output is correct