QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386249 | #7453. rplexq | alpha1022 | TL | 807ms | 39952kb | C++14 | 3.2kb | 2024-04-11 14:32:54 | 2024-04-11 14:32:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5;
const int B = 500;
const int C = (N - 1) / B + 1;
int n, m, rt;
vector<int> e[N + 5], ch[N + 5];
int fa[N + 5], siz[N + 5], id[N + 5], rk[N + 5];
bool heavy[N + 5];
void dfs1(int u) {
static int tot = 0;
rk[id[u] = ++tot] = u, siz[u] = 1;
for (int v : e[u])
if (v != fa[u])
fa[v] = u, ch[u].push_back(v), dfs1(v), siz[u] += siz[v];
sort(ch[u].begin(), ch[u].end(), [](int x, int y) { return siz[x] > siz[y]; });
for (int i = 0; i < B && i < ch[u].size(); ++i) heavy[ch[u][i]] = 1;
}
struct SqrtDecomposition {
int pos[N + 5], val[N + 5], sum[C + 5];
void init(int n) { for (int i = 1; i <= n; ++i) pos[i] = (i - 1) / B + 1; }
void update(int x, int k) {
for (int i = x; i <= min(pos[x] * B, n); ++i) val[i] += k;
for (int p = pos[x] + 1; p <= pos[n]; ++p) sum[p] += k;
}
int query(int x) { return val[x] + sum[pos[x]]; }
int query(int l, int r) { return query(r) - query(l - 1); }
} sd;
ll ans[N + 5];
vector<tuple<int, int, int, int, int>> qry[N + 5];
void dfs2(int u) {
for (auto &[l, r, id, pre0, pre1] : qry[u]) pre0 = sd.query(l, r);
if (heavy[u])
for (auto &[l, r, id, pre0, pre1] : qry[fa[u]]) pre1 = sd.query(l, r);
sd.update(u, 1);
for (int v : ch[u]) dfs2(v);
for (auto &[l, r, id, pre0, pre1] : qry[u]) {
int tmp = sd.query(l, r) - pre0;
ans[id] += (ll)tmp * (tmp - 1) / 2;
}
if (heavy[u])
for (auto &[l, r, id, pre0, pre1] : qry[fa[u]]) {
int tmp = sd.query(l, r) - pre1;
ans[id] -= (ll)tmp * (tmp - 1) / 2;
}
}
int cnt[N + 5];
int main() {
scanf("%d%d%d", &n, &m, &rt);
for (int i = 2; i <= n; ++i) {
int u, v; scanf("%d%d", &u, &v), e[u].push_back(v), e[v].push_back(u);
}
dfs1(rt);
for (int i = 1; i <= m; ++i) {
int l, r, u; scanf("%d%d%d", &l, &r, &u), qry[u].emplace_back(l, r, i, 0, 0);
}
sd.init(n), dfs2(rt);
for (int u = 1; u <= n; ++u) {
if (B >= ch[u].size()) continue;
vector<pair<int, int>> vec;
for (int j = B; j < ch[u].size(); ++j) {
int v = ch[u][j];
for (int k = id[v]; k < id[v] + siz[v]; ++k) vec.emplace_back(rk[k], v);
}
sort(vec.begin(), vec.end());
int block = sqrt(vec.size());
for (auto &[l, r, id, _, __] : qry[u])
l = lower_bound(vec.begin(), vec.end(), make_pair(l, 0)) - vec.begin(),
r = upper_bound(vec.begin(), vec.end(), make_pair(r, n)) - vec.begin() - 1;
sort(qry[u].begin(), qry[u].end(), [&](const tuple<int, int, int, int, int> &a, const tuple<int, int, int, int, int> &b) {
return get<0>(a) / block != get<0>(b) / block ? get<0>(a) < get<0>(b) : ~(get<0>(a) / block) & 1 ? get<1>(a) < get<1>(b) : get<1>(a) > get<1>(b);
});
fill_n(cnt + 1, n, 0);
int tl = 0, tr = -1; ll cur = 0;
for (auto &[l, r, id, _, __] : qry[u]) {
while (tr < r) cur += cnt[vec[++tr].second]++;
while (tl > l) cur += cnt[vec[--tl].second]++;
while (tr > r) cur -= --cnt[vec[tr--].second];
while (tl < l) cur -= --cnt[vec[tl++].second];
ans[id] -= cur;
}
}
for (int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 17876kb
input:
10 10 10 5 9 7 5 1 5 3 9 2 5 8 7 10 8 6 8 4 10 3 10 2 2 3 9 2 5 4 5 10 9 2 6 5 2 6 5 2 8 8 2 10 2 8 10 9 5 8 7
output:
0 0 0 0 3 3 9 0 0 1
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 4ms
memory: 17952kb
input:
10 10 7 4 2 10 4 3 2 6 10 9 2 7 3 1 4 8 2 5 3 8 10 10 2 6 2 3 6 2 4 6 4 3 10 2 8 8 10 3 10 4 2 3 2 2 6 4 1 7 10
output:
0 2 0 1 7 0 2 0 1 0
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 276ms
memory: 39952kb
input:
200000 200000 90409 124478 160846 171209 124478 192187 171209 180973 171209 189328 160846 184111 124478 199344 189328 172039 124478 159104 160846 197860 172039 180695 172039 147726 184111 176666 192187 156513 180695 53186 159104 109596 199344 173759 147726 155003 160846 186531 172039 147629 172039 1...
output:
1208 507 9154 54 45 27 67 1321 1910 176574 3 168 5 449 4773 9 19 368 5415 2882 388297 12452 563 0 6 4088 0 2585 660 30 15 30 25 13 87363 26 168 554 729 33 0 454 118 98 17546 169 27 1709 1386 36 14 1178 2110 0 1 0 486 0 891 84975 1091 586 52 138 857 46562 91193 167 21890 31156 33 1575 9024 242 728 22...
result:
ok 200000 numbers
Test #4:
score: 0
Accepted
time: 807ms
memory: 39304kb
input:
200000 200000 30609 170171 175523 175437 175523 38764 170171 151317 175523 120732 175437 170236 38764 192246 170236 148014 175523 170214 175523 174149 120732 177275 175523 172858 170171 192655 38764 156503 175523 180293 170214 162551 175523 144233 170171 150893 174149 107574 170171 177524 151317 161...
output:
19739 252249 253552 198701 316493 39544 273230 838431 126153 11216 35898 958434407 13123 14420 1 287730 438527 8116 3647487 671435 13122 5937 300 90 11833 114824 39321 7304 50301 175918 602062 97772162 12682 249 380315 510366 496238 3913170 4540 175512 571292 249060 3994808431 52833 7258777324 44901...
result:
ok 200000 numbers
Test #5:
score: -100
Time Limit Exceeded
input:
200000 200000 180733 188782 186482 190313 186482 122261 186482 177117 190313 182123 122261 190242 186482 130129 122261 198934 186482 194104 190242 184586 177117 193228 182123 158179 186482 186306 190313 152183 158179 192614 194104 197754 198934 119863 193228 189652 190313 189229 177117 192940 197754...