oj.uz

Submission #817587

# Submission time Handle Problem Language Result Execution time Memory
817587 2023-08-09T13:47:27 Z RecursiveCo Factories (JOI14_factories) C++14
100 / 100
 7031 ms 218728 KB 
// CF template, version 3.0

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

// #define int long long int

int power2(int v) {
    return 1<<__lg(v - 1) + 1;
}

struct LazySegtree {
    int n;
    vector<long long> tree;
    vector<long long> lazy;
    vector<long long> initial;

    LazySegtree(int N, vector<long long>& given)
    : n(power2(N)), tree(2 * n), lazy(2 * n) {
        forto(N, i) initial.push_back(given[i]);
    }

    void apply(long long add, int v) {
        tree[v] += add;
        lazy[v] += add;
    }

    void propagate(int v) {
        apply(lazy[v], 2 * v);
        apply(lazy[v], 2 * v + 1);
        lazy[v] = 0;
    }

    void build(int v, int l, int r) {
        if (l == r) {
            tree[v] = initial[l];
        } else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = min(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int ql, int qr, long long add, int v, int l, int r) {
        if (ql <= l && r <= qr) {
            apply(add, v);
        } else if (qr < l || r < ql) {
            return;
        } else {
            propagate(v);
            int middle = (l + r) / 2;
            upd(ql, qr, add, 2 * v, l, middle);
            upd(ql, qr, add, 2 * v + 1, middle + 1, r);
            tree[v] = min(tree[2 * v], tree[2 * v + 1]);
        }
    }

    long long query(int ql, int qr, int v, int l, int r) {
        if (ql <= l && r <= qr) {
            return tree[v];
        } else if (qr < l || r < ql) {
            return 3e18;
        } else {
            propagate(v);
            int middle = (l + r) / 2;
            long long left = query(ql, qr, 2 * v, l, middle);
            long long right = query(ql, qr, 2 * v + 1, middle + 1, r);
            return min(left, right);
        }
    }
};

vector<vector<array<int, 2>>> adjList;
vector<bool> visited;
vector<long long> height;
vector<vector<int>> paths;
vector<int> sz;
vector<bool> upward;
vector<bool> downward;
vector<bool> already;
vector<int> parent;
vector<int> indices;
vector<int> which;
vector<LazySegtree> segtrees;

void findvals(int v, int p, int w) {
    visited[v] = true;
    if (p == -1) {
        height[v] = 0;
    } else {
        height[v] = height[p] + w;
    }
    sz[v] = 1;
    int maxsz = 0;
    int maxnode = 0;
    for (array<int, 2> con: adjList[v]) {
        int node = con[0];
        int weight = con[1];
        if (!visited[node]) {
            findvals(node, v, weight);
            sz[v] += sz[node];
            parent[node] = v;
            if (sz[node] > maxsz) {
                maxsz = sz[node];
                maxnode = node;
            }
        }
    }
    if (maxsz >= (sz[v] + 1) / 2) {
        upward[maxnode] = true;
        downward[v] = true;
    }
}

void hld() {
    int n = adjList.size();
    int cnt = 0;
    upward[0] = false;
    forto(n, i) {
        if (!downward[i] && !already[i]) {
            vector<int> path;
            vector<long long> heights;
            int node = i;
            path.push_back(node);
            heights.push_back(-2LL * height[node]);
            indices[node] = 0;
            which[node] = cnt;
            int c = 0;
            while (upward[node] && !already[node]) {
                already[node] = true;
                node = parent[node];
                path.push_back(node);
                heights.push_back(-2LL * height[node]);
                indices[node] = ++c;
                which[node] = cnt;
            }
            already[node] = true;
            paths.push_back(path);
            LazySegtree tree(path.size(), heights);
            tree.build(1, 0, path.size() - 1);
            segtrees.push_back(tree);
            cnt++;
        }
    }
}

void Init(int n, int A[], int B[], int D[]) {
    adjList.resize(n);
    forto(n - 1, i) {
        int a = A[i];
        int b = B[i];
        int d = D[i];
        adjList[a].push_back({b, d});
        adjList[b].push_back({a, d});
    }
    visited.resize(n, false);
    height.resize(n);
    sz.resize(n);
    upward.resize(n, false);
    downward.resize(n, false);
    parent.resize(n, -1);
    indices.resize(n);
    which.resize(n);
    already.resize(n, false);
    findvals(0, -1, -1);
    hld();
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<array<long long, 2>> sorted;
    forto(T, i) {
        sorted.push_back({height[Y[i]], Y[i]});
    }
    sortl(sorted);
    vector<array<long long, 4>> updates;
    for (array<long long, 2> p: sorted) {
        long long h = p[0];
        int node = p[1];
        int thepath = which[node];
        int index = indices[node];
        while (1) {
            int last = paths[thepath].back();
            int sz = paths[thepath].size();
            if (segtrees[thepath].query(index, index, 1, 0, sz - 1) != -2LL * height[paths[thepath][index]]) break;
            if (segtrees[thepath].query(sz - 1, sz - 1, 1, 0, sz - 1) != -2LL * height[last]) {
                int l = index;
                int r = sz;
                while (r - l > 1) {
                    int middle = (l + r) / 2;
                    if (segtrees[thepath].query(middle, middle, 1, 0, sz - 1) != -2LL * height[paths[thepath][middle]]) r = middle;
                    else l = middle;
                }
                segtrees[thepath].upd(index, l, h - (long long) 1e18, 1, 0, sz - 1);
                updates.push_back({thepath, index, l, -h + (long long) 1e18});
                break;
            } else {
                segtrees[thepath].upd(index, sz - 1, h - (long long) 1e18, 1, 0, sz - 1);
                updates.push_back({thepath, index, sz - 1, -h + (long long) 1e18});
                if (last == 0) {
                    break;
                }
                int next = parent[last];
                thepath = which[next];
                index = indices[next];
            }
        }
    }
    long long ans = 3e18;
    forto(S, i) {
        long long h = height[X[i]];
        int node = X[i];
        long long from = 3e18;
        int thepath = which[node];
        int index = indices[node];
        while (1) {
            int last = paths[thepath].back();
            int sz = paths[thepath].size();
                from = min(from, segtrees[thepath].query(index, sz - 1, 1, 0, sz - 1) + h + (long long) 1e18);
                if (last == 0) {
                    break;
                }
                int next = parent[last];
                thepath = which[next];
                index = indices[next];
        }
        ans = min(ans, from);
    }
    for (array<long long, 4> update: updates) {
        int thepath = update[0];
        int l = update[1];
        int r = update[2];
        long long add = update[3];
        int sz = paths[thepath].size();

        segtrees[thepath].upd(l, r, add, 1, 0, sz - 1);
    }
    return ans;
}

Compilation message

factories.cpp: In function 'int power2(int)':
factories.cpp:22:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   22 |     return 1<<__lg(v - 1) + 1;
      |               ~~~~~~~~~~~~^~~
factories.cpp: In constructor 'LazySegtree::LazySegtree(int, std::vector<long long int>&)':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
factories.cpp:33:9: note: in expansion of macro 'forto'
   33 |         forto(N, i) initial.push_back(given[i]);
      |         ^~~~~
factories.cpp: In function 'void hld()':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
factories.cpp:133:5: note: in expansion of macro 'forto'
  133 |     forto(n, i) {
      |     ^~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
factories.cpp:163:5: note: in expansion of macro 'forto'
  163 |     forto(n - 1, i) {
      |     ^~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
factories.cpp:185:5: note: in expansion of macro 'forto'
  185 |     forto(T, i) {
      |     ^~~~~
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
factories.cpp:223:5: note: in expansion of macro 'forto'
  223 |     forto(S, i) {
      |     ^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 924 KB Output is correct
2 Correct 445 ms 19228 KB Output is correct
3 Correct 1022 ms 19004 KB Output is correct
4 Correct 919 ms 18936 KB Output is correct
5 Correct 1868 ms 19236 KB Output is correct
6 Correct 267 ms 19652 KB Output is correct
7 Correct 1080 ms 18952 KB Output is correct
8 Correct 663 ms 19400 KB Output is correct
9 Correct 1878 ms 19256 KB Output is correct
10 Correct 255 ms 19716 KB Output is correct
11 Correct 1037 ms 19036 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2494 ms 164572 KB Output is correct
3 Correct 3859 ms 139860 KB Output is correct
4 Correct 1055 ms 203664 KB Output is correct
5 Correct 5038 ms 161396 KB Output is correct
6 Correct 3836 ms 145336 KB Output is correct
7 Correct 3370 ms 47292 KB Output is correct
8 Correct 545 ms 60156 KB Output is correct
9 Correct 3674 ms 47420 KB Output is correct
10 Correct 3352 ms 48160 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 924 KB Output is correct
2 Correct 445 ms 19228 KB Output is correct
3 Correct 1022 ms 19004 KB Output is correct
4 Correct 919 ms 18936 KB Output is correct
5 Correct 1868 ms 19236 KB Output is correct
6 Correct 267 ms 19652 KB Output is correct
7 Correct 1080 ms 18952 KB Output is correct
8 Correct 663 ms 19400 KB Output is correct
9 Correct 1878 ms 19256 KB Output is correct
10 Correct 255 ms 19716 KB Output is correct
11 Correct 1037 ms 19036 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2494 ms 164572 KB Output is correct
14 Correct 3859 ms 139860 KB Output is correct
15 Correct 1055 ms 203664 KB Output is correct
16 Correct 5038 ms 161396 KB Output is correct
17 Correct 3836 ms 145336 KB Output is correct
18 Correct 3370 ms 47292 KB Output is correct
19 Correct 545 ms 60156 KB Output is correct
20 Correct 3674 ms 47420 KB Output is correct
21 Correct 3352 ms 48160 KB Output is correct
22 Correct 3319 ms 172980 KB Output is correct
23 Correct 3544 ms 174044 KB Output is correct
24 Correct 3849 ms 155472 KB Output is correct
25 Correct 4182 ms 159380 KB Output is correct
26 Correct 6209 ms 148648 KB Output is correct
27 Correct 5632 ms 168936 KB Output is correct
28 Correct 1283 ms 218728 KB Output is correct
29 Correct 7031 ms 147856 KB Output is correct
30 Correct 6621 ms 147644 KB Output is correct
31 Correct 6682 ms 148076 KB Output is correct
32 Correct 3126 ms 50492 KB Output is correct
33 Correct 635 ms 65272 KB Output is correct
34 Correct 1193 ms 48460 KB Output is correct
35 Correct 1151 ms 48488 KB Output is correct
36 Correct 2654 ms 45228 KB Output is correct
37 Correct 2689 ms 45356 KB Output is correct