Submission #1092107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092107		simona1230	Inside information (BOI21_servers)	C++17	5 / 100	3568 ms	53244 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];
vector<int> q[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};
            q[x].push_back(i);
        }
        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 sz[maxn];
int used[maxn];

void dfsz(int i,int p)
{
    sz[i]=1;

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

        dfsz(nb.x,i);
        sz[i]+=sz[nb.x];
    }
}

int all;

int cent(int i,int p)
{
    for(edge nb: v[i])
    {
        if(nb.x==p||used[nb.x])continue;

        if(sz[nb.x]>all/2)return cent(nb.x,i);
    }

    return i;
}

void incdfs(int i,int last,int p)
{
    update(1,1,n+k,last,1);
    for(edge nb: v[i])
    {
        if(nb.x==p||nb.id<last||used[nb.x])continue;
        incdfs(nb.x,nb.id,i);
    }
}

void decdfs(int i,int last,int p,int f)
{
    //cout<<i<<endl;
    for(int id: q[i])
    {
        ans[id]+=query(1,1,n+k,1,id);
        if(f<id)ans[id]++;
    }

    for(edge nb: v[i])
    {
        if(nb.x==p||nb.id>last||used[nb.x])continue;
        decdfs(nb.x,nb.id,i,f);
    }
}

void solve(int beg)
{
    memset(t,0,sizeof(t));
    dfsz(beg,-1);
    all=sz[beg];

    int c=cent(beg,-1);
    //cout<<"! "<<c<<endl;
    used[c]=1;

    for(edge e: v[c])
    {
        int nb=e.x;
        if(used[nb])continue;

        decdfs(nb,e.id,c,e.id);
        incdfs(nb,e.id,c);
    }

    for(int id: q[c])
    {
        ans[id]+=query(1,1,n+k,1,id);
    }

    for(edge e: v[c])
    {
        int nb=e.x;
        if(!used[nb])solve(nb);
    }
}

void print()
{
    for(int i=1; i<=n+k-1; i++)
    {
        if(a[i].c=='Q')
            cout<<typeQ(i,a[i].x,a[i].y)<<endl;
        else if(a[i].c=='C')
            cout<<ans[i]+1<<endl;
    }
}

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

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

    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

9 5
S 2 3
S 1 2
C 3
C 2
S 2 4
C 2
S 1 5
S 5 7
S 6 9
S 6 8
C 5
C 6
S 5 6

3
3
4
3
3
*/

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