Submission #1091967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091967		simona1230	Inside information (BOI21_servers)	C++17	52.50 / 100	374 ms	44664 KiB

servers

#include <bits/stdc++.h>

using namespace std;
const int maxn=240001;

struct input
{
    char c;
    int x,y;
    input() {}
    input(char _c,int _x,int _y)
    {
        c=_c;
        x=_x;
        y=_y;
    }
};

int n,k;
input a[maxn];

void read()
{
    cin>>n>>k;
    for(int i=1; i<=n+k-1; i++)
    {
        char c;
        int x,y;

        cin>>c;

        if(c=='C')
        {
            cin>>x;
            a[i]= {c,x,0};
        }
        else
        {
            cin>>x>>y;
            a[i]= {c,x,y};
        }
    }
}

struct edge
{
    int x,id;
    edge() {}
    edge(int _x,int _id)
    {
        x=_x;
        id=_id;
    }
};

vector<edge> v[maxn];

void cons()
{
    for(int i=1; i<=n+k-1; i++)
    {
        if(a[i].c=='S')
        {
            v[a[i].x].push_back({a[i].y,i});
            v[a[i].y].push_back({a[i].x,i});
        }
    }
}

int tmr,in[maxn],out[maxn];
int w[maxn],dec_[maxn],inc[maxn];
int jump[maxn][32],lvl[maxn];

void dfs1(int i,int p)
{
    if(p==1)inc[i]=dec_[i]=p;
    else
    {
        if(w[p]<w[i])dec_[i]=dec_[p],inc[i]=p;
        else inc[i]=inc[p],dec_[i]=p;
    }
    lvl[i]=lvl[p]+1;

    sort(v[i].begin(),v[i].end(),[](const edge& e1,const edge& e2)
    {
        return e1.id>e2.id;
    });

    in[i]=++tmr;

    for(edge e: v[i])
    {
        if(e.x==p)continue;

        w[e.x]=e.id;
        jump[e.x][0]=i;
        dfs1(e.x,i);
    }

    out[i]=tmr;
}

void prec()
{
    for(int j=1;j<=20;j++)
    {
        for(int i=1;i<=n;i++)
        {
            jump[i][j]=jump[jump[i][j-1]][j-1];
        }
    }
}

int make_jump(int i,int k)
{
    for(int j=0;j<=20;j++)
    {
        if((1<<j)&k)
            i=jump[i][j];
    }

    return i;
}

int lca(int x,int y)
{
    if(lvl[x]>lvl[y])swap(x,y);
    y=make_jump(y,lvl[y]-lvl[x]);
    if(x==y)return x;

    for(int i=20;i>=0;i--)
    {
        if(jump[x][i]!=jump[y][i])
        {
            x=jump[x][i];
            y=jump[y][i];
        }
    }

    return jump[x][0];
}

string typeQ(int i,int x,int y)
{
    if(x==y)return "yes";

    int z=lca(x,y);
    int l=lvl[z];

    int l1=dec_[x];
    int l2=inc[y];

    int xx=y,yy=x;
    if(lvl[yy]==l)
    {
        xx=make_jump(xx,lvl[xx]-lvl[yy]-1);
        if(w[xx]>i)return "no";
    }
    else if(w[yy]>i)return "no";

    if(lvl[l1]<=l&&lvl[l2]<=l)
    {
        if(lvl[x]==l||lvl[y]==l)return "yes";

        x=make_jump(x,lvl[x]-l-1);
        y=make_jump(y,lvl[y]-l-1);

        if(w[x]>w[y])return "yes";
    }
    return "no";
}

int ans[maxn];
int t[4*maxn];

void update(int i,int l,int r,int idx,int val)
{
    if(l==r)
    {
        t[i]+=val;
        return;
    }

    int m=(l+r)/2;
    if(idx<=m)update(i*2,l,m,idx,val);
    else update(i*2+1,m+1,r,idx,val);
    t[i]=t[i*2]+t[i*2+1];
}

int query(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[i];
    int m=(l+r)/2;
    return query(i*2,l,m,ql,min(qr,m))+query(i*2+1,m+1,r,max(ql,m+1),qr);
}

int act(int x,int i)
{
    int y=lvl[x]-lvl[inc[x]]-1;
    int l=0,r=y,ans=0;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(w[make_jump(x,m)]<=i)
        {
            ans=m+1;
            l=m+1;
        }
        else r=m-1;
    }

    return make_jump(x,ans);
}

void solve()
{
    for(int i=1;i<=n+k-1;i++)
    {
        if(a[i].c=='S')
        {
            if(lvl[a[i].x]<lvl[a[i].y])swap(a[i].x,a[i].y);
            update(1,1,n,in[a[i].x],1);
            //cout<<"+ "<<in[a[i].x]<<" "<<a[i].x<<endl;
            a[i].y=dec_[a[i].x];
            if(a[i].y!=1)
            {
                //cout<<"- "<<in[jump[a[i].y][0]]<<endl;
                update(1,1,n,in[jump[a[i].y][0]],-1);
            }
        }
        else if(a[i].c=='Q')cout<<typeQ(i,a[i].x,a[i].y)<<endl;
        else if(a[i].c=='C')
        {
            int x=a[i].x;
            int up=act(x,i);
            int rem=query(1,1,n,in[x],in[x]);
            int xx=x;
            while(xx!=up)rem+=query(1,1,n,in[jump[x][0]],in[jump[x][0]]),xx=jump[xx][0];
            cout<<query(1,1,n,in[up],out[x])+lvl[x]-lvl[up]+1-rem<<endl;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    read();
    cons();
    dfs1(1,1);
    prec();
    solve();

    return 0;
}
/*
9 5
S 1 4
S 4 7
S 3 5
Q 1 7
Q 7 1
S 3 6
Q 5 6
Q 6 5
S 2 1
S 7 9
S 7 8
S 1 3
Q 4 6
*/

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5