제출 #950835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950835		vjudge1	Tourism (JOI23_tourism)	C++17	28 / 100	5081 ms	32868 KiB

tourism

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct AINT {
    int n;
    vector<ii> V; /// (minim, cnt)
    vi Lz;

    ii join(ii a, ii b) {
        if(a.first == b.first)
            return {a.first, a.second + b.second};
        return min(a, b);
    }

    AINT(int N) : n(N), V(4 * N), Lz(4 * N) {}

    void init(int u, int s, int d) {
        if(s == d) {
            V[u] = {0, 1};
            return;
        }
        init(u << 1, s, (s + d) >> 1);
        init(u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = join(V[u << 1], V[u << 1 | 1]);
    }

    void init() { init(1, 0, n - 1); }

    void propag(int u, int s, int d) {
        if(!Lz[u]) return;
        V[u].first += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void update(int l, int r, int v, int u, int s, int d) {
        propag(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            Lz[u] += v;
            propag(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = join(V[u << 1], V[u << 1 | 1]);
    }

    void update(int l, int r, int v) { update(l, r, v, 1, 0, n - 1); }

    int query() { /// nr de 0 uri
        if(V[1].first == 0) return V[1].second;
        return 0;
    }
};

struct tree {
    int n, tmr = 0;
    vi par, niv, sz, nxt, in;
    vector<vi> L, G, Anc;

    AINT A;

    tree(int N) : n(N), par(N), niv(N), sz(N, 0), 
    nxt(N, 0), in(N, 0), L(N), G(N), A(N) {} /// nxt[u] e capul la lant

    void add_edge(int u, int v) {
        L[u].push_back(v);
        L[v].push_back(u);
    }

    void init() {
        function<void(int, int, int)> dfs0 = [&](int u, int p, int li) {
            par[u] = p;
            niv[u] = li;
            sz[u] = 1;
            for (auto it : L[u])
                if (it != p) {
                    dfs0(it, u, li + 1);
                    sz[u] += it;
                    G[u].push_back(it);
                }
        };
        dfs0(0, -1, 0);

        A.init();

        function<void(int, int)> dfs1 = [&](int u, int p) {
            sort(all(G[u]), [&](auto a, auto b) { return sz[a] > sz[b]; });
            in[u] = tmr++;
            if (G[u].empty()) return;
            nxt[G[u][0]] = nxt[u];
            dfs1(G[u][0], u);
            for (int i = 1; i < G[u].size(); ++i) {
                nxt[G[u][i]] = G[u][i];
                dfs1(G[u][i], u);
            }
        };
        dfs1(0, -1);
        
        Anc.push_back(par);
        for (int k = 1; (1 << k) <= n; ++k) {
            Anc.push_back(vi(n, -1));
            for (int i = 0; i < n; ++i) {
                Anc[k][i] = Anc[k - 1][i] == -1 ? -1 : Anc[k - 1][Anc[k - 1][i]];
            }
        }
    }

    int lift(int u, int nr) {
        for (int i = 0; i < (int)Anc.size(); ++i)
            if (nr & (1 << i))
                u = Anc[i][u];
        return u;
    }

    int lca(int u, int v) {
        if(niv[u] > niv[v]) swap(u, v);
        v = lift(v, niv[v] - niv[u]);
        if(u == v) return u;
        for(int i = (int)Anc.size() - 1; i >= 0; --i)
            if(Anc[i][u] != Anc[i][v]) {
                u = Anc[i][u];
                v = Anc[i][v];
            }
        return par[u];
    }

    void update(int u, int v) {
        while(u != -1) {
            A.update(min(in[u], in[nxt[u]]), max(in[u], in[nxt[u]]), v);
            u = par[nxt[u]];
        }
    }

    int query() { /// nr pornite
        return n - A.query();
    }
};

struct RMQ_LCA {
    int m;
    tree &T;
    vi C;
    vector<vi> Re;

    RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
        Re.push_back(C);
        for(int k = 1; (1 << k) <= m; ++k) {
            Re.push_back(vi(m, 0));
            for(int i = 0; i < m; ++i) {
                if(i + (1 << (k - 1)) < m)
                    Re[k][i] = T.lca(Re[k - 1][i], Re[k - 1][i + (1 << (k - 1))]);
                else Re[k][i] = Re[k - 1][i];
            }
        }
    }

    int query(int st, int dr) {
        int l = 31 - __builtin_clz(dr - st + 1);
        return T.lca(Re[l][st], Re[l][dr - (1 << l) + 1]);
    }
};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    tree T(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        T.add_edge(u, v);
    }
    T.init();
    vi C(m);
    for(int i = 0; i < m; ++i) {
        cin >> C[i];
        --C[i];
    }

    RMQ_LCA Stramos(n, C, T);

    //TODO MO
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        for (int j = l; j <= r; ++j)
            T.update(C[j], 1);
        int nr0 = T.query();
        int nr_plus = T.niv[Stramos.query(l, r)];
        cout << nr0 - nr_plus << "\n";
        for (int j = l; j <= r; ++j)
            T.update(C[j], -1);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp: In lambda function:
tourism.cpp:110:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             for (int i = 1; i < G[u].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~
tourism.cpp: In constructor 'RMQ_LCA::RMQ_LCA(int, vi, tree&)':
tourism.cpp:160:8: warning: 'RMQ_LCA::C' will be initialized after [-Wreorder]
  160 |     vi C;
      |        ^
tourism.cpp:159:11: warning:   'tree& RMQ_LCA::T' [-Wreorder]
  159 |     tree &T;
      |           ^
tourism.cpp:163:5: warning:   when initialized here [-Wreorder]
  163 |     RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
      |     ^~~~~~~

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