제출 #950835

#제출 시각아이디문제언어결과실행 시간메모리
950835vjudge1Tourism (JOI23_tourism)C++17
28 / 100
5081 ms32868 KiB
#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) {
      |     ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...