Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162#1. 第二个 A + B ProblemNagoriYuuuki10013ms3492kbC++233.3kb2025-04-17 14:29:412025-04-19 16:15:17

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
#define endl '\n'

class LinkCutTree
{
public:
    struct Node
    {
        int fa;
        array<int, 2> son;
        bool rev;
        int sum, val;
        Node() : fa(0), son({0, 0}), rev(false), sum(0), val(0) {}
    };
    vector<Node> tree;

    bool isroot(int x)
    {
        int fa = tree[x].fa;
        return tree[fa].son[0] != x && tree[fa].son[1] != x;
    }

    void pushup(int x)
    {
        int ls = tree[x].son[0], rs = tree[x].son[1];
        tree[x].sum = tree[x].val + tree[ls].sum + tree[rs].sum;
    }

    void pushrev(int x)
    {
        if (!x)
            return;
        swap(tree[x].son[0], tree[x].son[1]);
        tree[x].rev ^= 1;
    }

    void pushdown(int x)
    {
        if (tree[x].rev)
        {
            pushrev(tree[x].son[0]);
            pushrev(tree[x].son[1]);
            tree[x].rev = 0;
        }
    }

    void push(int x)
    {
        if (!isroot(x))
            push(tree[x].fa);
        pushdown(x);
    }

    void rotate(int x)
    {
        int y = tree[x].fa;
        int z = tree[y].fa;
        int k = tree[y].son[1] == x;
        if (!isroot(y))
            tree[z].son[tree[z].son[1] == y] = x;
        tree[x].fa = z;
        tree[y].son[k] = tree[x].son[k ^ 1];
        if (tree[x].son[k ^ 1])
            tree[tree[x].son[k ^ 1]].fa = y;
        tree[y].fa = x;
        tree[x].son[k ^ 1] = y;
        pushup(y);
    }

    void splay(int x)
    {
        int y, z;
        push(x);
        while (!isroot(x))
        {
            y = tree[x].fa;
            z = tree[y].fa;
            if (!isroot(y))
                tree[z].son[0] == y ^ tree[y].son[0] == x ? rotate(x) : rotate(y);
            rotate(x);
        }
        pushup(x);
    }

    void access(int x)
    {
        for (int y = 0; x; y = x, x = tree[x].fa)
        {
            splay(x);
            tree[x].son[1] = y;
            pushup(x);
        }
    }

    void makeroot(int x)
    {
        access(x);
        splay(x);
        pushrev(x);
    }

    void split(int x, int y)
    {
        makeroot(x);
        access(y);
        splay(y);
    }

    void link(int x, int y)
    {
        makeroot(x);
        tree[x].fa = y;
    }

    void cut(int x, int y)
    {
        makeroot(x);
        access(y);
        splay(y);
        if (tree[y].son[0] != x || tree[x].son[1])
            return;
        tree[x].fa = tree[y].son[0] = 0;
        pushup(y);
    }

    int findroot(int x)
    {
        access(x);
        splay(x);
        while (tree[x].son[0])
        {
            pushdown(x);
            x = tree[x].son[0];
        }
        pushdown(x);
        return x;
    }

    LinkCutTree(int n, vector<int> &arr) : tree(n + 1)
    {
        for (int i = 1; i <= n; i++)
            tree[i].val = tree[i].sum = arr[i];
    }
};

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n = 2;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    LinkCutTree lct(n, arr);
    lct.link(1, 2);
    lct.split(1, 2);
    lct.pushup(2);
    cout << lct.tree[2].sum << endl;

    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 3ms
memory: 3432kb

input:

23 24

output:

47

result:

ok 1 number(s): "47"

Test #2:

score: 10
Accepted
time: 1ms
memory: 3372kb

input:

233 1

output:

234

result:

ok 1 number(s): "234"

Test #3:

score: 10
Accepted
time: 1ms
memory: 3320kb

input:

222 333

output:

555

result:

ok 1 number(s): "555"

Test #4:

score: 10
Accepted
time: 1ms
memory: 3376kb

input:

1 333

output:

334

result:

ok 1 number(s): "334"

Test #5:

score: 10
Accepted
time: 1ms
memory: 3312kb

input:

222 333

output:

555

result:

ok 1 number(s): "555"

Test #6:

score: 10
Accepted
time: 0ms
memory: 3436kb

input:

242 333

output:

575

result:

ok 1 number(s): "575"

Test #7:

score: 10
Accepted
time: 1ms
memory: 3376kb

input:

222 3330

output:

3552

result:

ok 1 number(s): "3552"

Test #8:

score: 10
Accepted
time: 1ms
memory: 3376kb

input:

2220 333

output:

2553

result:

ok 1 number(s): "2553"

Test #9:

score: 10
Accepted
time: 3ms
memory: 3492kb

input:

222 555

output:

777

result:

ok 1 number(s): "777"

Test #10:

score: 10
Accepted
time: 1ms
memory: 3232kb

input:

222 3333

output:

3555

result:

ok 1 number(s): "3555"

Extra Test:

score: 0
Extra Test Passed