Submission #1091582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091582		simona1230	Inside information (BOI21_servers)	C++17	50 / 100	265 ms	43688 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 t,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]=++t;

    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]=t;
}

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";
}

void solve()
{
    for(int i=1;i<=n+k-1;i++)
    {
        if(a[i].c=='Q')cout<<typeQ(i,a[i].x,a[i].y)<<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: 0 / 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