QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137202 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | ckiseki | 0 | 458ms | 65940kb | C++23 | 7.5kb | 2023-08-10 04:02:05 | 2023-08-10 04:02:07 |
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) {
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) {
return;
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: 32ms
memory: 5108kb
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: 458ms
memory: 65940kb
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
Time Limit Exceeded
Test #25:
score: 0
Time Limit Exceeded
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%