ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#162 | #1. 第二个 A + B Problem | NagoriYuuuki | 100 | 13ms | 3492kb | C++23 | 3.3kb | 2025-04-17 14:29:41 | 2025-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