QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137201 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ckiseki | 0 | 734ms | 197800kb | C++23 | 7.5kb | 2023-08-10 03:52:29 | 2023-08-10 03:52:30 |
Judging History
answer
// An AC a day keeps the doctor away.
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
int cnt = sizeof...(T);
((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
using namespace std;
using lld = int64_t;
struct Centroid {
vector<vector<int>> &g;
vector<vector<pair<int, lld&>>> qs;
vector<int> vis, sz;
vector<int> dis;
Centroid(vector<vector<int>> &t_g) : g(t_g), qs(g.size()),
vis(g.size()), sz(g.size()), dis(g.size()) {
}
void solve() {
decomp(0, 0);
}
void add_query(int i, int d, lld &a) {
qs[i].emplace_back(d, a);
}
void get_size(vector<int> &s, int i) {
s.emplace_back(i);
vis[i] = true;
sz[i] = 1;
for (int j: g[i]) if (!vis[j]) {
get_size(s, j);
sz[i] += sz[j];
}
}
void dfs(vector<int> &s, int i) {
s.emplace_back(i);
vis[i] = true;
for (int j: g[i]) if (!vis[j]) {
dis[j] = dis[i] + 1;
dfs(s, j);
}
}
void gao(const vector<int> &vtx, int coef) {
int mx = 0;
for (int x: vtx) mx = max(mx, dis[x]);
vector<int> pre(mx + 1);
for (int x: vtx) {
pre[dis[x]] += 1;
mx = max(mx, dis[x]);
}
for (int i = 1; i <= mx; i++) pre[i] += pre[i - 1];
for (int x: vtx) {
for (auto &[d, p]: qs[x]) {
// #{ y | dis[x] + dis[y] <= d }
int cnt = d - dis[x] < 0 ? 0 : pre[min(mx, d - dis[x])];
p += coef * cnt;
}
}
}
void decomp(int i, int d) {
vector<int> s;
get_size(s, i);
int c = -1;
for (int j: s) {
if (sz[j] * 2 >= sz[i])
c = j;
vis[j] = false;
}
vis[c] = true;
vector<int> total;
vector<vector<int>> sub;
for (int j: g[c]) {
if (vis[j]) continue;
dis[j] = 1;
sub.emplace_back();
dfs(sub.back(), j);
for (int x: sub.back())
total.emplace_back(x);
}
dis[c] = 0;
total.emplace_back(c);
gao(total, 1);
for (const auto &t: sub) gao(t, -1);
for (int j: s) vis[j] = false;
vis[c] = true;
for (int j: g[c]) {
if (vis[j]) continue;
decomp(j, d + 1);
}
}
};
struct HLD {
vector<vector<int>> &g;
vector<vector<tuple<int, int, lld&>>> g_qs;
vector<vector<tuple<int, int, lld&>>> f_qs;
vector<int> vis, sz, mxs, top, pa, dep;
int dfc;
vector<int> tin, tou, ord;
int64_t totsum;
vector<int> sum;
HLD(vector<vector<int>> &t_g) : g(t_g),
g_qs(g.size()), f_qs(g.size()),
vis(g.size()), sz(g.size()), mxs(g.size()), top(g.size()), pa(g.size()), dep(g.size()),
dfc(0), tin(g.size()), tou(g.size()), ord(g.size()),
totsum(0), sum(g.size() + 1) {
get_size(0, -1);
make_chain(0, -1, 0);
}
void get_size(int i, int f) {
sz[i] = 1; mxs[i] = -1;
for (int j: g[i]) {
if (j == f) continue;
pa[j] = i;
dep[j] = dep[i] + 1;
get_size(j, i);
sz[i] += sz[j];
if (mxs[i] == -1 || sz[mxs[i]] < sz[j])
mxs[i] = j;
}
}
void make_chain(int i, int f, int t) {
ord[dfc] = i;
tin[i] = dfc++;
top[i] = t;
if (mxs[i] != -1) make_chain(mxs[i], i, t);
for (int j: g[i]) {
if (j == f) continue;
if (j == mxs[i]) continue;
make_chain(j, i, j);
}
tou[i] = dfc;
}
void add_f_query(int u, int d, int coef, lld &ans) {
if (d < 0) return;
ans += coef * (sz[u] - 1);
f_qs[tou[u]-1].emplace_back(dep[u] + d + 1, -coef, ans);
f_qs[tin[u]].emplace_back(dep[u] + d + 1, coef, ans);
// for (int t = tin[u] + 1; t < tou[u]; t++) {
// int v = ord[t];
// // if (dep[v] - dep[u] <= d) {
// // ans += coef;
// // }
// }
}
void do_f_query(int n) {
vector<int64_t> cnt(n);
for (int i = 0; i < n; i++) {
cnt[ dep[ord[i]] ] += sz[ord[i]];
for (auto &[d, coef, ans]: f_qs[i])
ans += coef * (d >= 0 && d < n ? cnt[d] : 0);
}
}
int add_query(int x, int y, int d, lld &ans) {
g_qs[x].emplace_back(d, 1, ans);
g_qs[y].emplace_back(d, 1, ans);
if (mxs[x] != -1) add_f_query(mxs[x], d - 1, 1, ans);
if (mxs[y] != -1) add_f_query(mxs[y], d - 1, 1, ans);
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
int t = top[x];
add_f_query(t, d - 1, -1, ans);
add_f_query(mxs[pa[t]], d - 1, 1, ans);
x = pa[t];
}
int z = dep[x] < dep[y] ? x : y;
g_qs[z].emplace_back(d, -2, ans);
return z;
}
void dfs_g(int i, int f) {
totsum += sz[i];
for (int j: g[i]) {
if (j == f || j == mxs[i]) continue;
for (int t = tin[j]; t < tou[j]; t++) {
int u = ord[t];
sum[ dep[u] - dep[i] ] += sz[u];
}
}
for (auto &[d, coef, ans]: g_qs[i]) {
int64_t cur = totsum - dep[i] - sum[d + 1];
debug(ans, coef, cur);
ans += coef * cur;
}
for (int j: g[i]) {
if (j == f) continue;
dfs_g(j, i);
}
totsum -= sz[i];
for (int j: g[i]) {
if (j == f || j == mxs[i]) continue;
for (int t = tin[j]; t < tou[j]; t++) {
int u = ord[t];
sum[ dep[u] - dep[i] ] -= sz[u];
}
}
}
void solve() {
dfs_g(0, -1);
do_f_query(g.size());
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
int q;
cin >> q;
vector<lld> ans(q);
Centroid cent(g);
HLD hld(g);
for (int i = 0; i < q; i++) {
int x, y, d;
cin >> x >> y >> d;
--x, --y;
int z = hld.add_query(x, y, d, ans[i]);
cent.add_query(z, d, ans[i]);
debug(x+1, y+1, z+1);
// hld.add_query(z, d, -2, ans[i]);
// hld.add_query(x, d, 1, ans[i]);
// hld.add_query(y, d, 1, ans[i]);
}
cent.solve();
hld.solve();
for (int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 7448kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
7620 6603 14092 2594 1717 9385 8743 6702 13158 5289 3886 2429 12215 3802 11433 12136 12718 3036 12207 2281 5760 11537 12994 8262 2115 3409 13540 12094 2763 8127 2192 8836 3162 6220 2585 8602 4821 787 2821 10820 8165 2591 2595 11107 13119 4675 11536 12980 3945 2761 3148 1827 2849 6968 12774 10668 372...
result:
wrong answer 1st numbers differ - expected: '3226', found: '7620'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 488ms
memory: 73268kb
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
759 69428 2797 181264 91719 182 32496 199183 6399 15975 11640 119051 236 689 17 9540 41 36592 178938 56 45424 193403 90248 3417 949 102 34135 60471 199861 188090 75088 127 1 6 4 3 3 11 61157 199860 199163 155706 196289 192862 53742 51862 179199 428 196282 199989 3635 26 99007 134461 198159 20382 751...
result:
wrong answer 1st numbers differ - expected: '757', found: '759'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 734ms
memory: 197800kb
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
65454 190036 357161 116281 301958 310180 15709 209342 2451 166313 153308 4315 149727 409443 79772 464370 82407 447028 381249 125033 349579 267828 10004 393003 131603 111883 237347 206646 270032 4502 406997 75797 138707 373325 185597 62854 358761 470940 156226 369853 427647 447927 49019 185025 168621...
result:
wrong answer 1st numbers differ - expected: '78', found: '65454'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%