Submission #1031514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031514		Wael	Tourism (JOI23_tourism)	C++17	100 / 100	695 ms	88256 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct SegmentTree {
    int n;
    vector<int> sum;
    SegmentTree(int n) : n(n) {
        sum.assign(4 * n, 0);
    }

    void update(int i, int v) {
        update(i, v, 0, 0, n - 1);
    }   
    void update(int i, int v, int x, int lx, int rx) {
        if (lx == rx) {
            sum[x] += v;
            return;
        }
        int mid = (lx + rx) / 2;
        if (i <= mid) {
            update(i, v, 2 * x + 1, lx, mid);            
        } else {
            update(i, v, 2 * x + 2, mid + 1, rx);
        }
        sum[x] = sum[2 * x + 1] + sum[2 * x + 2];
    }

    int get(int l, int r) {
        return get(l, r, 0, 0, n - 1);
    }
    int get(int l, int r, int x, int lx, int rx) {
        if (lx > r || rx < l) return 0;
        if (l <= lx && rx <= r) return sum[x];
        int mid = (lx + rx) / 2;
        return get(l, r, 2 * x + 1, lx, mid) + get(l, r, 2 * x + 2, mid + 1, rx);
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> c(m);
    vector<vector<int>> indices(n);
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
        --c[i];
        indices[c[i]].push_back(i);
    }

    vector<int> l(q), r(q);
    for (int i = 0; i < q; ++i) {
        cin >> l[i] >> r[i];
        --l[i], --r[i];
    }

    vector<int> dep(n), sz(n);
    function<void(int, int)> calc = [&](int u, int p) {
        for (int i = 0; i < adj[u].size(); ++i) {
            if (adj[u][i] == p) {
                swap(adj[u][i], adj[u].back());
                adj[u].pop_back();
                break;
            }
        }

        sz[u] = 1;
        for (auto v : adj[u]) {
            dep[v] = dep[u] + 1;
            calc(v, u);
            sz[u] += sz[v];
        }

        for (int i = 1; i < adj[u].size(); ++i) {
            if (sz[adj[u][i]] > sz[adj[u][0]]) {
                swap(adj[u][i], adj[u][0]);
            }
        }
    };
    calc(0, -1);

    vector<set<array<int, 4>>> st(n);
    vector<vector<pair<int, int>>> update(m);
    
    auto addRange = [&](int l, int r, int v) {
        if (l > r) return;
        update[l].push_back({l, v});
        if (r + 1 < m) {
          update[r + 1].push_back({l, -v});
        }
    };

    int const inf = 1e9;
    auto append = [&](int u, int l, int r) {
        auto it = prev(st[u].upper_bound(array{l, inf, inf, inf}));
        auto [L, R, d, t] = *it;
        addRange(L, R, d - dep[u]);
        if (L == l && r == R && l > 0 && r + 1 < m) {
            auto itL = prev(it);
            auto itR = next(it);
            addRange((*itL)[0], (*itL)[1], (*itL)[2] - dep[u] + 1);
            addRange((*itR)[0], (*itR)[1], (*itR)[2] - dep[u] + 1);
            int nl = (*itL)[0], nr = (*itR)[1];
            st[u].erase(it);
            st[u].erase(itL);
            st[u].erase(itR);
            st[u].insert(array{nl, nr, dep[u] - 1, 1});
        } else if (L == l && l > 0) {
            auto itL = prev(it);
            auto [cl, cr, cd, ct] = *itL;
            addRange(cl, cr, cd - dep[u] + 1);
            int nl = cl, nr = r;
            st[u].erase(it);
            st[u].erase(itL);
            st[u].insert(array{nl, nr, dep[u] - 1, 1});
            if (r < R) {
                st[u].insert(array{r + 1, R, dep[u], 0});
            }
        } else if (r == R && r + 1 < m) {
            auto itR = next(it);
            auto [cl, cr, cd, ct] = *itR;
            addRange(cl, cr, cd - dep[u] + 1);
            int nl = l, nr = cr;
            st[u].erase(it);
            st[u].erase(itR);
            st[u].insert(array{nl, nr, dep[u] - 1, 1});
            if (L < l) {
                st[u].insert(array{L, l - 1, dep[u], 0});
            }
        } else {
            st[u].erase(it);
            st[u].insert(array{l, r, dep[u] - 1, 1});
            if (L < l) {
                st[u].insert(array{L, l - 1, dep[u], 0});
            }
            if (r < R) {
                st[u].insert(array{r + 1, R, dep[u], 0});
            }
        }
    };

    function<void(int)> dfs = [&](int u) {
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i];
            dfs(v);
            if (i == 0) {
                swap(st[u], st[v]);
            } else {
                for (auto [l, r, d, t] : st[v]) {
                    if (t == 1) {
                        addRange(l, r, d - dep[u] + 1);
                        append(u, l, r);
                    } else {
                        addRange(l, r, d - dep[v] + 1);
                    }
                }
                set<array<int, 4>>().swap(st[v]);
            }
        }
        if (st[u].size() == 0) {
            st[u] = {{0, m - 1, dep[u], 0}};
        }
        for (auto i : indices[u]) {
            append(u, i, i);
        }
    };      
    dfs(0);
    for (auto [l, r, d, t] : st[0]) {
        addRange(l, r, d - dep[0] + 1);
    }

    vector<vector<int>> query(m);
    for (int i = 0; i < q; ++i) {
        query[r[i]].push_back(i);
    }

    vector<int> ans(q);
    SegmentTree seg(m);
    for (int i = 0; i < m; ++i) {
        for (auto [j, v] : update[i]) {
            seg.update(j, v);
        }
        for (auto j : query[i]) {
            ans[j] = n - seg.get(0, l[j]);
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

tourism.cpp: In lambda function:
tourism.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i = 0; i < adj[u].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
tourism.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 1; i < adj[u].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
tourism.cpp: In lambda function:
tourism.cpp:153:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         for (int i = 0; i < adj[u].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41