QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733606 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | londono | 0 | 1306ms | 217016kb | C++14 | 8.3kb | 2024-11-10 20:04:47 | 2024-11-10 20:04:51 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = (int)2e5+5;
int n; vector<int> G[MAXN];
namespace LCA{
const int stp = 17;
int fa[MAXN][stp+1], dep[MAXN];
void dfs_build(int x) {
dep[x] ++;
for (int i = 1; i <= stp; i++) {
fa[x][i] = fa[fa[x][i-1]][i-1];
}
for (int to : G[x]) {
if (to == fa[x][0]) continue;
dep[to] = dep[x];
fa[to][0] = x;
dfs_build(to);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = stp; i >= 0; i--) {
if (dep[fa[x][i]] >= dep[y]) {
x = fa[x][i];
}
}
if (x == y) return x;
for (int i = stp; i >= 0; i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int dist(int x, int y) {
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
}
int m, ans[MAXN];
struct qr{ int d, k; int i; };
vector<qr> qsf[MAXN], qf[MAXN], qg[MAXN];
namespace TSG{
int fa[MAXN], hson[MAXN], dep[MAXN], siz[MAXN];
void dfs1(int x) {
dep[x] ++; siz[x] = 1;
for (int to : G[x]) {
if (to == fa[x]) continue;
fa[to] = x; dep[to] = dep[x];
dfs1(to);
siz[x] += siz[to];
if (siz[to] > siz[hson[x]]) {
hson[x] = to;
}
}
}
int top[MAXN];
void dfs2(int x, int tp) {
top[x] = tp;
for (int to : G[x]) {
if (to == fa[x]) continue;
dfs2(to, (to==hson[x]?tp:to));
}
}
void addRF(int x, int d, int k, int i) {
ans[i] += LCA::dep[x];
qg[x].push_back({d, k, i});
if (d == 0) return;
if (hson[x] && d)
qf[hson[x]].push_back({d-1, k, i});
while (1) {
x = top[x];
if (x == 1) break;
qf[x].push_back({d-1, -k, i});
qf[hson[fa[x]]].push_back({d-1, k, i});
x = fa[x];
}
}
}
void init() {
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
}
void addSF(int x, int d, int k, int i) {
qsf[x].push_back({d, k, i});
}
void dealqry() {
cin >> m;
for (int i = 1, u, v, d, t; i <= m; i++) {
cin >> u >> v >> d;
t = LCA::lca(u, v);
TSG::addRF(u, d, 1, i);
TSG::addRF(v, d, 1, i);
TSG::addRF(t, d, -2, i);
addSF(t, d, 1, i);
}
}
namespace getf{
const int MAXL = MAXN*20*2;
int rt[MAXN];
int sum[MAXL], lc[MAXL], rc[MAXL], pt;
void modify(int p, int l, int r, int x, int v) {
sum[p] += v;
if (l == r) return;
int mid = l + r >> 1;
if (x <= mid) {
if (!lc[p]) lc[p] = ++pt;
modify(lc[p], l, mid, x, v);
} else {
if (!rc[p]) rc[p] = ++pt;
modify(rc[p], mid+1, r, x, v);
}
}
int merge(int p, int q, int l, int r) {
if (!p || !q) return p | q;
int mid = l + r >> 1;
sum[p] += sum[q];
lc[p] = merge(lc[p], lc[q], l, mid);
rc[p] = merge(rc[p], rc[q], mid+1, r);
return p;
}
int query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return sum[p];
int mid = l + r >> 1, res = 0;
if (ql <= mid) res += query(lc[p], l, mid, ql, qr);
if (mid < qr) res += query(rc[p], mid+1, r, ql, qr);
return res;
}
void calc(int x, int fa, int dep) {
rt[x] = ++pt;
modify(rt[x], 1, n, dep, 1);
for (int to : G[x]) {
if (to == fa) continue;
calc(to, x, dep+1);
rt[x] = merge(rt[x], rt[to], 1, n);
}
for (qr _ : qf[x]) {
ans[_.i] += query(rt[x], 1, n, dep, dep+_.d) * _.k;
}
}
}
namespace getg{
#define lowbit(x) ((x)&-(x))
struct arr{
int t[MAXN], d[MAXN], ti;
int& operator [] (int x) {
if (t[x] != ti) {
t[x] = ti;
d[x] = 0;
}
return d[x];
}
}bit;
void mdf(int x, int v) {
for (; x <= n; x+=lowbit(x)) {
bit[x] += v;
}
}
int qry(int x) {
int sum = 0;
for (; x; x-=lowbit(x))
sum += bit[x];
return sum;
}
void insert(int x, int fa, int dep) {
mdf(dep, 1);
for (int to : G[x]) {
if (to == fa) continue;
insert(to, x, dep+1);
}
}
void calc(int x, int fa, int dep) {
bit.ti++;
for (int to : G[x]) {
if (to == fa || to == TSG::hson[x]) continue;
insert(to, x, 1);
}
for (qr _ : qf[x]) {
ans[_.i] += qry(_.d)*_.k;
}
for (int to : G[x]) {
if (to == fa) continue;
calc(to, x, dep+1);
}
}
}
namespace getsf{
#define vi vector<int>
bool vis[MAXN];
int siz[MAXN], all;
void dfssiz(int x, int fa) {
siz[x] = 1;
for (int to : G[x]) {
if (to == fa || vis[to]) continue;
dfssiz(to, x);
siz[x] += siz[to];
}
}
int dfsmid(int x, int fa) {
int mx = all - siz[x];
for (int to : G[x]) {
if (to == fa || vis[to]) continue;
int tmp = dfsmid(to, x);
if (tmp) return tmp;
mx = max(mx, siz[to]);
}
return x*(mx*2<=all);
}
int Tfa[MAXN];
int findmid(int x) {
dfssiz(x, 0);
all = siz[x];
return dfsmid(x, 0);
}
vi b[MAXN], fb[MAXN];
void mdf(vi& bit, int x, int v) {
for (; x < bit.size(); x+=lowbit(x)) {
bit[x] += v;
}
}
int qry(vi& bit, int x) {
int res = 0;
for (; x; x-=lowbit(x)) {
res += bit[x];
}
return res;
}
int dfs_mxdep(int x, int fa) {
int res = 0;
for (int to : G[x]) {
if (to == fa || vis[to]) continue;
res = max(res, dfs_mxdep(to, x));
}
return res+1;
}
void insert(vi v, int x, int fa, int dep) {
mdf(v, dep, 1);
for (int to : G[x]) {
if (to == fa || vis[to]) continue;
insert(v, to, x, dep+1);
}
}
void build(int x) {
vis[x] = 1;
b[x].resize(dfs_mxdep(x, 0)+1);
insert(b[x], x, 0, 1);
for (int to : G[x]) {
if (vis[to]) continue;
int tr = findmid(to);
Tfa[tr] = x;
fb[tr].resize(dfs_mxdep(to, 0)+1);
insert(fb[tr], to, 0, 2);
build(tr);
}
}
void calc() {
build(findmid(1));
for (int i = 1; i <= n; i++) {
if (qsf[i].empty()) continue;
int now = i, pre = 0;
while (now) {
for (qr _ : qsf[i]) {
int nd = _.d - LCA::dist(now, i);
if (nd < 0) continue;
ans[_.i] += qry(b[now], nd+1)*_.k;
if (pre) ans[_.i] -= qry(fb[pre], nd+1);
}
pre = now; now = Tfa[now];
}
}
}
}
void print() {
for (int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
}
int main() {
// g++ code.cpp -o code.exe -std=c++14 -O2 -fno-ms-extensions "-Wl,--stack=1000000000" -DLOCAL; ./code
time_t stm = clock();
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("ans.out", "w", stdout);
#else
// freopen("tii.in", "r", stdin);
// freopen("tii.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
init();
LCA::dfs_build(1);
TSG::dfs1(1);
TSG::dfs2(1, 1);
dealqry();
getf::calc(1, 1, 1);
getg::calc(1, 1, 1);
getsf::calc();
print();
cerr << "Exec Time: " << (double)(clock()-stm)/CLOCKS_PER_SEC << "s" << endl;
return 0;
}
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: 49284kb
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:
-1090 -763 -4573 16 0 -2293 -1926 -635 -4028 -138 9 36 -3310 3 -1194 -1379 -3759 60 -3326 14 -335 -1138 -4280 -2358 21 17 -4670 -1742 12 -1603 7 -813 48 -210 28 -1618 -185 -32 19 -791 -1592 13 19 -2372 -4024 -10 -3349 -3477 22 -36 14 8 5 -646 -3907 -2624 17 -755 -8 14 -599 -30 -3458 -6 -1868 -400 17...
result:
wrong answer 1st numbers differ - expected: '3226', found: '-1090'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 1306ms
memory: 217016kb
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:
33 86 47 -37 106 39 52 76 53 1 89 66 36 -3 58 11 21 73 -5 37 33 112 33 114 -28 30 31 1 144 -2 -81 2003493398 33 65 42 36 21 39 -8 69 -9 64 -15 4 4 49 164 59 6169 -2010191759 42 51 36 17 108 9 59 89 61 45 113 49 34 36 37 28 30 63 -1999144876 31 114 -19 72 78 61 42 58 73 24 15 56 36 2005150143 21 9169...
result:
wrong answer 1st numbers differ - expected: '757', found: '33'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1121ms
memory: 192744kb
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:
16 -31028 -29135 -555 -41248 -44334 -1211 -43998 24 -1373 23 19 5 -127919 27 -114622 -1 -133410 -26178 -793 -36589 -14205 23 -91332 -7122 42 -23030 -7933 -31519 27 -94734 33 23 -44300 -189 -503 -44444 -81344 -3 -33976 -71967 -128849 -2402 -4571 -21516 -102663 -29071 17 25 -69 -145633 -90001 -4839 -1...
result:
wrong answer 1st numbers differ - expected: '78', found: '16'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%