QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#416174 | #5403. 树数术 | chroneZ | 20 | 2474ms | 299880kb | C++17 | 3.9kb | 2024-05-21 16:46:32 | 2024-05-21 16:46:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 7e5 + 10;
int n; vector<int> G[N];
namespace Tree {
int dep[N], siz[N], son[N], fa[N], top[N], dfn[N], dn;
inline void dfs1(int u) {
son[u] = -1, siz[u] = 1;
for(auto v : G[u]) {
if(v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v);
siz[u] += siz[v];
if(son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
}
}
int seq[N << 1], m, fir[N];
inline void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++dn;
seq[++m] = u; fir[u] = m;
if(son[u] == -1) return;
dfs2(son[u], t);
seq[++m] = u;
for(auto v : G[u]) {
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
seq[++m] = u;
}
}
inline bool subt(int u, int v) {
return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + siz[u];
}
int st[21][N << 1];
inline void buildst() {
for(int i = 1; i <= m; i++) {
st[0][i] = seq[i];
}
for(int i = 1; i <= 20; i++) {
for(int j = 1; j + (1 << i) - 1 <= m; j++) {
int l = st[i - 1][j], r = st[i - 1][j + (1 << i - 1)];
st[i][j] = dep[l] < dep[r] ? l : r;
}
}
}
inline int lca(int u, int v) {
int l = fir[u], r = fir[v];
if(l > r) swap(l, r);
int L = __lg(r - l + 1);
int x = st[L][l], y = st[L][r - (1 << L) + 1];
return dep[x] < dep[y] ? x : y;
}
void build() {
dfs1(1), dfs2(1, 1);
assert(m == 2 * n - 1);
buildst();
}
}
using Tree::subt, Tree::lca;
int m, Q, a[N];
struct Info {
int A, res;
int id, l, r;
};
vector<Info> res;
struct SegmentTree {
Info t[N << 2];
inline int calc(int k, int l, int r, int p) {
if(l == r) return subt(t[k].A, p);
// if(subt(p, t[k].A) && p != t[k].A) return 0;
int mid = l + r >> 1;
// if(subt(p, t[k << 1].A) && p != t[k << 1].A) return calc(k << 1 | 1, mid + 1, r, p);
// else return calc(k << 1, l, mid, p) + t[k].res - t[k << 1].res;
if(subt(t[k << 1].A, p)) return calc(k << 1, l, mid, p) + t[k].res - t[k << 1].res;
else return calc(k << 1 | 1, mid + 1, r, lca(t[k << 1].A, p));
}
inline void build(int k, int l, int r) {
t[k].id = k, t[k].l = l, t[k].r = r;
if(l == r) {
t[k].A = a[l];
t[k].res = 1;
return;
}
int mid = l + r >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
t[k].A = lca(t[k << 1].A, t[k << 1 | 1].A);
t[k].res = t[k << 1].res + calc(k << 1 | 1, mid + 1, r, t[k << 1].A);
}
inline void query(int k, int l, int r, int x, int y) {
if(x <= l && r <= y) return res.push_back(t[k]), void();
int mid = l + r >> 1;
if(x <= mid) query(k << 1, l, mid, x, y);
if(mid < y) query(k << 1 | 1, mid + 1, r, x, y);
}
} tr;
int L[N], R[N];
inline void read(int &x) {
char ch = getchar(); x = 0;
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
}
int main() {
// freopen("tree.in", "r", stdin);
// freopen("tree.out", "w", stdout);
// ios::sync_with_stdio(false);
// cin.tie(nullptr), cout.tie(nullptr);
read(n), read(m), read(Q);
for(int i = 1; i < n; i++) {
int u, v; read(u), read(v);
G[u].push_back(v), G[v].push_back(u);
}
Tree::build();
for(int i = 1; i <= m; i++) {
read(a[i]);
}
tr.build(1, 1, m);
while(Q--) {
int k; read(k);
res.clear();
vector<pair<int, int>> S;
for(int i = 1; i <= k; i++) {
read(L[i]), read(R[i]);
S.emplace_back(L[i], R[i]);
}
sort(S.begin(), S.end());
for(auto [l, r] : S) {
tr.query(1, 1, m, l, r);
}
for(int i = 1; i < res.size(); i++) {
res[i].A = lca(res[i - 1].A, res[i].A);
res[i].res = res[i - 1].res + tr.calc(res[i].id, res[i].l, res[i].r, res[i - 1].A);
}
printf("%d\n", res.back().res);
}
// cerr << clock() * 1e3 / CLOCKS_PER_SEC << " ms\n";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2474ms
memory: 299880kb
input:
699990 699995 233333 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
414919 464289 494925 386270 442147 364276 401975 454211 431471 299450 366103 265439 325816 163975 348433 216139 401719 16634 200359 27351 103756 169847 290266 463858 339876 150935 151290 229206 198892 444771 398455 419146 293826 372006 432125 80459 385306 415228 62365 222331 474164 276309 284536 238...
result:
wrong answer 1st lines differ - expected: '121987', found: '414919'
Subtask #2:
score: 20
Accepted
Test #2:
score: 20
Accepted
time: 2152ms
memory: 261344kb
input:
699992 699994 699992 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 40 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
211594 160846 176729 128251 32662 70710 74884 9095 68282 91324 154262 24279 31878 173468 75265 139715 91660 87525 194302 16875 81535 172911 29145 20483 151883 5255 9548 58890 38076 94152 14358 74859 48870 23981 41390 60976 13795 125823 427 26641 130620 174231 73241 55291 2364 78864 23391 4866 36002 ...
result:
ok 699992 lines
Subtask #3:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 141ms
memory: 102092kb
input:
99998 99993 33333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 24 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 49 ...
output:
9733 11330 8403 5136 22207 23231 12686 27288 23739 20937 18153 16379 8991 14036 11669 14685 20272 18955 21680 7927 21383 23576 14834 5714 15707 10013 7905 13254 13883 10446 16140 16796 11009 11912 15761 20419 11157 12192 14327 18260 19095 5239 4114 16522 7412 5005 16844 8747 19377 22600 12023 9161 9...
result:
wrong answer 33324th lines differ - expected: '23208', found: '30931'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%