QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386220 | #7453. rplexq | alpha1022 | ML | 0ms | 29360kb | C++14 | 3.2kb | 2024-04-11 14:13:28 | 2024-04-11 14:13:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5;
const int B = 300;
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];
void dfs(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), dfs(v), siz[u] += siz[v];
sort(ch[u].begin(), ch[u].end(), [](int x, int y) { return siz[x] > siz[y]; });
}
struct SqrtDecomposition {
static const int B = 447;
static const int C = (N - 1) / B + 1;
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>> tqry;
vector<tuple<int, int, int, int>> opt[N + 5];
vector<tuple<int, int, int>> qry[N + 5];
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);
}
dfs(rt);
auto insertQuery = [&](int l, int r, int u, int w, int qid) {
opt[id[u]].emplace_back(l, r, 1, tqry.size()), opt[id[u] + siz[u]].emplace_back(l, r, -1, tqry.size()),
tqry.emplace_back(w, qid, 0);
};
for (int i = 1; i <= m; ++i) {
int l, r, u; scanf("%d%d%d", &l, &r, &u), insertQuery(l, r, u, 1, i);
for (int j = 0; j < B && j < ch[u].size(); ++j) insertQuery(l, r, ch[u][j], -1, i);
qry[u].emplace_back(l, r, i);
}
sd.init(n);
for (int i = n; i; --i) {
sd.update(rk[i], 1);
for (auto [l, r, w, id] : opt[i]) get<2>(tqry[id]) += sd.query(l, r) * w;
}
for (auto [w, id, cur] : tqry) ans[id] += (ll)cur * (cur - 1) / 2 * w;
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(), [&](tuple<int, int, int> a, tuple<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: 0ms
memory: 29360kb
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: 0ms
memory: 29060kb
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: -100
Memory Limit Exceeded
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...