QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#137598 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ckiseki | 0 | 714ms | 202196kb | C++23 | 9.4kb | 2023-08-10 14:23:42 | 2023-08-10 14:23:45 |
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<int64_t> 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) {
pa[i] = f;
sz[i] = 1; mxs[i] = -1;
for (int j: g[i]) {
if (j == f) continue;
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) {
debug("ADD_F_QUERY", u+1, d, coef);
if (d < 0) return;
ans += coef * sz[u];
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);
// int cnt = 0;
// for (int t = tin[u]; t < tou[u]; t++) {
// int v = ord[t];
// if (dep[v] - dep[u] <= d) ++cnt;
// }
// debug(u+1, d, coef, cnt);
// ans += coef * cnt;
}
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);
for (int w: {x, y})
if (mxs[w] != -1)
add_f_query(mxs[w], d - 1, 1, ans);
int org_x = x, org_y = y;
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;
if (pa[z] != -1)
g_qs[pa[z]].emplace_back(d, -2, ans);
add_f_query(z, d, -2, ans);
int onchain = dep[org_x] + dep[org_y] - dep[z] * 2 + 2;
ans += onchain;
debug(onchain);
return z;
}
void dfs_g(int i, int f) {
if (mxs[i] != -1) {
totsum += sz[i] - 1 - sz[mxs[i]];
for (int t = tou[mxs[i]]; t < tou[i]; t++) {
int u = ord[t];
sum[ dep[u] - dep[i] ] += sz[u];
}
}
for (auto &[d, coef, ans]: g_qs[i]) {
// for (int x = i; x != -1; x = pa[x]) {
// int m = 0;
// if (mxs[x] != -1)
// for (int t = tou[mxs[x]]; t < tou[x]; t++) {
// int u = ord[t];
// debug(u);
// if (dep[u] - dep[x] == d + 1)
// m += sz[u];
// }
// debug(x+1, sz[x] - 1 - m, sz[x], m);
// }
debug(totsum, sum[d + 1]);
int64_t cur = totsum - sum[d + 1];
debug(coef, cur, d, i+1);
ans += coef * cur;
}
for (int j: g[i]) {
if (j == f) continue;
dfs_g(j, i);
}
if (mxs[i] != -1) {
totsum += sz[i] - 1 - sz[mxs[i]];
for (int t = tou[mxs[i]]; t < tou[i]; 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);
/* const auto brute = [&](int x, int y, int d) { */
/* const auto &p = hld.pa; */
/* const auto &dep = hld.dep; */
/* vector<int> dis(n, -1); */
/* queue<int> que; */
/* while (x != y) { */
/* if (dep[x] < dep[y]) swap(x, y); */
/* que.emplace(x); */
/* dis[x] = 0; */
/* x = p[x]; */
/* } */
/* que.emplace(x); */
/* dis[x] = 0; */
/* while (!que.empty()) { */
/* int i = que.front(); que.pop(); */
/* for (int j: g[i]) { */
/* if (dis[j] == -1) { */
/* dis[j] = dis[i] + 1; */
/* que.emplace(j); */
/* } */
/* } */
/* } */
/* int a = 0; */
/* for (int i = 0; i < n; i++) */
/* if (dis[i] <= d) */
/* ++a; */
/* return a; */
/* }; */
/* vector<lld> bans(q); */
for (int i = 0; i < q; i++) {
// int x = rand() % n;
// int y = rand() % n;
// int d = rand() % n;
int x, y, d;
cin >> x >> y >> d;
--x, --y;
// bans[i] = brute(x, y, d);
int z = hld.add_query(x, y, d, ans[i]);
cent.add_query(z, d, ans[i]);
// hld.add_query(z, d, -2, ans[i]);
// hld.add_query(x, d, 1, ans[i]);
// hld.add_query(y, d, 1, ans[i]);
}
hld.solve();
orange(all(ans));
cent.solve();
orange(all(ans));
// orange(all(bans));
// assert (ans == bans);
for (int i = 0; i < q; i++)
cout << ans[i] << '\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: 11ms
memory: 7472kb
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:
30010 17140 21702 2194 6418 7306 28872 21601 32634 17754 7662 21443 34308 9588 46728 41946 7588 36201 34311 12 22170 20913 28544 22488 19 7076 26816 39684 9202 17294 6304 19265 26992 27060 3697 25842 19231 1274 5814 43252 27008 5244 4693 29047 31316 19542 30230 31008 5167 9210 6463 5475 11401 19993 ...
result:
wrong answer 1st numbers differ - expected: '3226', found: '30010'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 552ms
memory: 83072kb
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:
757 69428 2793 181264 91707 318 32496 199183 6399 15983 11640 119051 236 689 15 9532 41 36592 181376 56 45524 193451 90248 3417 1313 112 34413 60471 199861 188090 75092 127 1 6 4 3 443 11 61157 199860 199153 155706 196287 193374 53802 51978 179199 428 196282 199989 3613 26 99007 134461 198159 20382 ...
result:
wrong answer 6th numbers differ - expected: '182', found: '318'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 714ms
memory: 202196kb
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:
279516 1237251 2658896 868154 1023681 1311194 125846 2021344 7963 588685 149035 132964 295518 1999451 25 1254148 484609 1954228 2641113 643071 2561429 423969 74777 2003130 1554764 380145 340714 2255199 2625525 8160 2368266 351995 111214 2340882 260295 357053 1309394 1440746 278649 1402744 1399289 19...
result:
wrong answer 1st numbers differ - expected: '78', found: '279516'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%