이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |