UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194785#1. A+B Problemxie_zhuzhu1000ms1188kbC++112.3kb2023-10-17 20:31:192023-10-17 20:31:20

answer

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
using namespace std;
struct node 
{
    int data,rev,sum;
    node *son[2],*pre;
    bool judge();
    bool isroot();
    void pushdown();
    void update();
    void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x)
{
    node *now=lct+ ++top;
    now->data=x;
    now->pre=now->son[1]=now->son[0]=lct;
    now->sum=0;
    now->rev=0;
    return now;
}
bool node::judge(){return pre->son[1]==this;}
bool node::isroot()
{
    if(pre==lct)return true;
    return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown()
{
    if(this==lct||!rev)return;
    swap(son[0],son[1]);
    son[0]->rev^=1;
    son[1]->rev^=1;
    rev=0;
}
void node::update(){sum=son[1]->sum+son[0]->sum+data;}
void node::setson(node *child,int lr)
{
    this->pushdown();
    child->pre=this;
    son[lr]=child;
    this->update();
}
void rotate(node *now)
{
    node *father=now->pre,*grandfa=father->pre;
    if(!father->isroot()) grandfa->pushdown();
    father->pushdown();now->pushdown();
    int lr=now->judge();
    father->setson(now->son[lr^1],lr);
    if(father->isroot()) now->pre=grandfa;
    else grandfa->setson(now,father->judge());
    now->setson(father,lr^1);
    father->update();now->update();
    if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
    if(now->isroot())return;
    for(;!now->isroot();rotate(now))
    if(!now->pre->isroot())
    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
    node *last=lct;
    for(;now!=lct;last=now,now=now->pre)
    {
        splay(now);
        now->setson(last,1);
    }
    return last;
}
void changeroot(node *now)
{
    access(now)->rev^=1;
    splay(now);
}
void connect(node *x,node *y)
{
    changeroot(x);
    x->pre=y;
    access(x);
}
void cut(node *x,node *y)
{
    changeroot(x);
    access(y);
    splay(x);
    x->pushdown();
    x->son[1]=y->pre=lct;
    x->update();
}
int query(node *x,node *y)
{
    changeroot(x);
    node *now=access(y);
    return now->sum;
}
int main()
{
    scanf("%d%d",&a,&b);
    node *A=getnew(a);
    node *B=getnew(b);
        connect(A,B);
        cut(A,B);
        connect(A,B);
    printf("%d\n",query(A,B)); 
    return 0;
}

详细

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

Test #1:

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

input:

23 24

output:

47

result:

ok single line: '47'

Test #2:

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

input:

233 1

output:

234

result:

ok single line: '234'

Test #3:

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

input:

222 333

output:

555

result:

ok single line: '555'

Test #4:

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

input:

1 333

output:

334

result:

ok single line: '334'

Test #5:

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

input:

222 333

output:

555

result:

ok single line: '555'

Test #6:

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

input:

242 333

output:

575

result:

ok single line: '575'

Test #7:

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

input:

222 3330

output:

3552

result:

ok single line: '3552'

Test #8:

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

input:

2220 333

output:

2553

result:

ok single line: '2553'

Test #9:

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

input:

222 555

output:

777

result:

ok single line: '777'

Test #10:

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

input:

222 3333

output:

3555

result:

ok single line: '3555'

Extra Test:

score: 0
Extra Test Passed