QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72847 | #4837. Ramen | ckiseki# | WA | 6ms | 15716kb | C++20 | 3.4kb | 2023-01-19 17:44:05 | 2023-01-19 17:44:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300025;
struct Fenwick {
int b[maxn];
int query(int l, int r) {
return query(r - 1) - query(l - 1);
}
void add(int p, int v) {
for (++p; p < maxn; p += p & -p)
b[p] += v;
}
int query(int p) {
int r = 0;
for (++p; p < maxn; p += p & -p)
r += b[p];
return r;
}
} BIT;
vector<int> g[maxn];
int pa[maxn][20], in[maxn], out[maxn];
int dep[maxn];
int tot;
void dfs(int i, int f) {
in[i] = tot++;
pa[i][0] = f;
for (int l = 0; l + 1 < 20; l++)
pa[i][l + 1] = pa[pa[i][l]][l];
for (int j: g[i]) {
if (j == f) continue;
dep[j] = dep[i] + 1;
dfs(j, i);
}
out[i] = tot;
}
int tmp[maxn];
int64_t pre[maxn];
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
for (int i = 0; i < 20; i++)
if (d >> i & 1)
x = pa[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--)
if (pa[x][i] != pa[y][i])
x = pa[x][i], y = pa[y][i];
return pa[x][0];
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs(1, 0);
cerr << "in, out = \n";
for (int i = 1; i <= n; i++) {
cerr << in[i] << ' ' << out[i] << endl;
}
cerr << endl;
vector<tuple<int,int,int>> evt;
// evt.reserve(n * (log(n) + 2));
for (int x = 1; x <= n; x++) {
for (int y = 1; x * y <= n && y < x; y++) {
evt.emplace_back(x * y, x, y);
}
}
for (int z = 1; z <= n; z++) {
evt.emplace_back(z, -1, -1);
}
sort(evt.begin(), evt.end());
for (const auto &[A, B, C]: evt) {
if (B == -1 && C == -1) {
int z = A;
int sum = 0;
for (int j: g[z]) {
if (j == pa[z][0]) continue;
cerr << "query " << j << endl;
tmp[j] = BIT.query(in[j], out[j]);
cerr << "tmp[j] = " << tmp[j] << endl;
sum += tmp[j];
}
for (int j: g[z]) {
if (j == pa[z][0]) continue;
int add = sum - tmp[j];
pre[in[j]] += add;
pre[out[j]] -= add;
}
{
int add = sum;
pre[in[z]] += add;
pre[in[z] + 1] -= add;
}
} else {
int x = B;
int y = C;
int l = LCA(x, y);
cerr << "x, y = " << x << ", " << y << endl;
cerr << "l = " << l << endl;
BIT.add(in[x], 1);
BIT.add(in[y], 1);
BIT.add(in[l], -2);
if (l > x * y) {
pre[0] += 1;
pre[in[l]] -= 1;
pre[out[l]] += 1;
pre[tot] -= 1;
}
}
}
for (int i = 1; i < tot; i++)
pre[i] += pre[i - 1];
for (int i = 1; i <= n; i++)
cout << 1LL * n * (n + 1) / 2 - pre[in[i]] << '\n';
return 0;
}
/*
5
1 2
4 2
2 5
3 5
in, out =
0 5
1 5
4 5
2 3
3 5
query 2
tmp[j] = 0
query 4
tmp[j] = 0
query 5
tmp[j] = 0
x, y = 2, 1
l = 1
x, y = 3, 1
l = 1
x, y = 4, 1
l = 1
query 3
tmp[j] = 3
x, y = 5, 1
l = 1
15
15
15
15
12
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 15716kb
input:
3 1 2 -5
output:
6 6 6
result:
wrong output format YES or NO expected, but 6 found