Submission #817587

#	Time	Username	Problem	Language	Result	Execution time	Memory
817587		RecursiveCo	Factories (JOI14_factories)	C++14	100 / 100	7031 ms	218728 KiB

factories

// 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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67