QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72848#4839. Smaller LCAckiseki#WA 807ms98940kbC++203.4kb2023-01-19 17:46:482023-01-19 17:46:51

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-19 17:46:51]
  • 评测
  • 测评结果:WA
  • 用时:807ms
  • 内存:98940kb
  • [2023-01-19 17:46:48]
  • 提交

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

*/

详细

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'