제출 #950883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950883		vjudge1	Tourism (JOI23_tourism)	C++17	10 / 100	5061 ms	43340 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;
    vi V;

    AINT(int N) : n(N), V(N, 1e9) {}
    
    void init() {

    }

    void update(int l, int r, int v, int u, int s, int d) {
        for(int i = l; i <= r; ++i) V[i] = v;
    }

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

    int query(int r) {
        int cnt = 0;
        for(auto it : V)
            if(it <= r) ++cnt;
        return cnt;
    }
};

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_lant(int l, int u, int val) { /// (l, u] update
        if(niv[l] == niv[u]) return;
        while(u != -1) {
            if(niv[nxt[u]] > niv[l]) {
                A.update(in[nxt[u]], in[u], val);
                u = par[nxt[u]];
            } else {
                A.update(in[l] + 1, in[u], val);
                break;
            }
        }
    }

    void update(int u, int v, int val) {
        int l = lca(u, v);
        update_lant(l, u, val);
        update_lant(l, v, val);
    }

    int query(int r) { /// nr chestii <= r
        return A.query(r);
    }
};

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);

    int rad = (int)round(sqrt(double(n)));
    vector<pair<ii, int> > Q;
    vi Re(q, 0);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        Q.push_back({ii{l, r}, i});
    }
    sort(all(Q));

    int ult = C.back();
    int p = int(Q.size()) - 1;
    for(int i = m - 1; i >= 0; --i) {
        T.update(ult, C[i], i + 1);
        ult = C[i];
        while(p >= 0 && Q[p].first.first == i) {
            auto [seg, id] = Q[p];
            auto [l, r] = seg;
            Re[id] = T.query(r);
            --p;
        }
    }

    for(auto it : Re)
        cout << it + 1 << "\n";
    return 0;
}

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

tourism.cpp: In lambda function:
tourism.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i = 1; i < G[u].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~
tourism.cpp: In constructor 'RMQ_LCA::RMQ_LCA(int, vi, tree&)':
tourism.cpp:140:8: warning: 'RMQ_LCA::C' will be initialized after [-Wreorder]
  140 |     vi C;
      |        ^
tourism.cpp:139:11: warning:   'tree& RMQ_LCA::T' [-Wreorder]
  139 |     tree &T;
      |           ^
tourism.cpp:143:5: warning:   when initialized here [-Wreorder]
  143 |     RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
      |     ^~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:182:9: warning: unused variable 'rad' [-Wunused-variable]
  182 |     int rad = (int)round(sqrt(double(n)));
      |         ^~~

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