QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72848 | #4839. Smaller LCA | ckiseki# | WA | 807ms | 98940kb | C++20 | 3.4kb | 2023-01-19 17:46:48 | 2023-01-19 17:46:51 |
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 > 0; 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: 100
Accepted
time: 1ms
memory: 17776kb
input:
5 1 2 4 2 2 5 3 5
output:
15 15 15 15 14
result:
ok 5 number(s): "15 15 15 15 14"
Test #2:
score: -100
Wrong Answer
time: 807ms
memory: 98940kb
input:
300000 40632 143306 32259 40632 225153 143306 269774 225153 289668 40632 191636 269774 85717 191636 58564 191636 156509 143306 289939 40632 247103 269774 40257 40632 98149 289668 142277 143306 291616 40257 46813 225153 56324 143306 277154 142277 53903 289668 114266 32259 152231 58564 241151 152231 4...
output:
44999437117 44999129259 44999137206 44999136225 44998457384 44999001687 44998753296 44998516397 44998429566 44998477307 44999123393 44998484641 44998625716 44999245174 44998935691 44998910739 44998469435 44998663203 44998674226 44998473272 44999076453 44998658754 44998904125 44998513412 44999310429 ...
result:
wrong answer 2nd numbers differ - expected: '44999604051', found: '44999129259'