oj.uz

Submission #1091949

# Submission time Handle Problem Language Result Execution time Memory
1091949 2024-09-22T17:05:09 Z simona1230 Inside information (BOI21_servers) C++17
52.5 / 100
 277 ms 41496 KB 
#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]);
            if(lvl[up]!=lvl[x])rem+=query(1,1,n,in[jump[x][0]],in[jump[x][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

# Verdict Execution time Memory Grader output
1 Correct 145 ms 7764 KB Output is correct
2 Correct 139 ms 8656 KB Output is correct
3 Correct 141 ms 8788 KB Output is correct
4 Correct 157 ms 8784 KB Output is correct
5 Correct 145 ms 8788 KB Output is correct
6 Correct 144 ms 8676 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 7764 KB Output is correct
2 Correct 139 ms 8656 KB Output is correct
3 Correct 141 ms 8788 KB Output is correct
4 Correct 157 ms 8784 KB Output is correct
5 Correct 145 ms 8788 KB Output is correct
6 Correct 144 ms 8676 KB Output is correct
7 Incorrect 142 ms 7652 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 134 ms 7760 KB Output is correct
2 Correct 210 ms 32704 KB Output is correct
3 Correct 199 ms 32740 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 134 ms 7760 KB Output is correct
2 Correct 210 ms 32704 KB Output is correct
3 Correct 199 ms 32740 KB Output is correct
4 Correct 135 ms 7760 KB Output is correct
5 Correct 208 ms 32704 KB Output is correct
6 Correct 186 ms 33220 KB Output is correct
7 Correct 194 ms 32964 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 7764 KB Output is correct
2 Correct 232 ms 41220 KB Output is correct
3 Correct 248 ms 41336 KB Output is correct
4 Correct 211 ms 41300 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 7764 KB Output is correct
2 Correct 232 ms 41220 KB Output is correct
3 Correct 248 ms 41336 KB Output is correct
4 Correct 211 ms 41300 KB Output is correct
5 Incorrect 131 ms 7840 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 7764 KB Output is correct
2 Correct 197 ms 32808 KB Output is correct
3 Correct 248 ms 33360 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 7764 KB Output is correct
2 Correct 197 ms 32808 KB Output is correct
3 Correct 248 ms 33360 KB Output is correct
4 Incorrect 135 ms 7760 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 7760 KB Output is correct
2 Correct 243 ms 41496 KB Output is correct
3 Correct 231 ms 41296 KB Output is correct
4 Correct 220 ms 41300 KB Output is correct
5 Correct 132 ms 7864 KB Output is correct
6 Correct 195 ms 32852 KB Output is correct
7 Correct 227 ms 33204 KB Output is correct
8 Correct 251 ms 33616 KB Output is correct
9 Correct 243 ms 33624 KB Output is correct
10 Correct 231 ms 38236 KB Output is correct
11 Correct 264 ms 37456 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 7760 KB Output is correct
2 Correct 243 ms 41496 KB Output is correct
3 Correct 231 ms 41296 KB Output is correct
4 Correct 220 ms 41300 KB Output is correct
5 Correct 132 ms 7864 KB Output is correct
6 Correct 195 ms 32852 KB Output is correct
7 Correct 227 ms 33204 KB Output is correct
8 Correct 251 ms 33616 KB Output is correct
9 Correct 243 ms 33624 KB Output is correct
10 Correct 231 ms 38236 KB Output is correct
11 Correct 264 ms 37456 KB Output is correct
12 Incorrect 133 ms 7776 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 7724 KB Output is correct
2 Correct 144 ms 8532 KB Output is correct
3 Correct 160 ms 8808 KB Output is correct
4 Correct 152 ms 8784 KB Output is correct
5 Correct 148 ms 8788 KB Output is correct
6 Correct 149 ms 8676 KB Output is correct
7 Correct 135 ms 7764 KB Output is correct
8 Correct 218 ms 32960 KB Output is correct
9 Correct 220 ms 32700 KB Output is correct
10 Correct 143 ms 7760 KB Output is correct
11 Correct 251 ms 41300 KB Output is correct
12 Correct 247 ms 41228 KB Output is correct
13 Correct 239 ms 41156 KB Output is correct
14 Correct 138 ms 7764 KB Output is correct
15 Correct 216 ms 32852 KB Output is correct
16 Correct 238 ms 33208 KB Output is correct
17 Correct 277 ms 33712 KB Output is correct
18 Correct 269 ms 33952 KB Output is correct
19 Correct 262 ms 38256 KB Output is correct
20 Correct 252 ms 37460 KB Output is correct
21 Correct 243 ms 32836 KB Output is correct
22 Correct 210 ms 32780 KB Output is correct
23 Correct 236 ms 33268 KB Output is correct
24 Correct 228 ms 33336 KB Output is correct
25 Correct 248 ms 35020 KB Output is correct
26 Correct 230 ms 32596 KB Output is correct
27 Correct 217 ms 32716 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 7724 KB Output is correct
2 Correct 144 ms 8532 KB Output is correct
3 Correct 160 ms 8808 KB Output is correct
4 Correct 152 ms 8784 KB Output is correct
5 Correct 148 ms 8788 KB Output is correct
6 Correct 149 ms 8676 KB Output is correct
7 Correct 135 ms 7764 KB Output is correct
8 Correct 218 ms 32960 KB Output is correct
9 Correct 220 ms 32700 KB Output is correct
10 Correct 143 ms 7760 KB Output is correct
11 Correct 251 ms 41300 KB Output is correct
12 Correct 247 ms 41228 KB Output is correct
13 Correct 239 ms 41156 KB Output is correct
14 Correct 138 ms 7764 KB Output is correct
15 Correct 216 ms 32852 KB Output is correct
16 Correct 238 ms 33208 KB Output is correct
17 Correct 277 ms 33712 KB Output is correct
18 Correct 269 ms 33952 KB Output is correct
19 Correct 262 ms 38256 KB Output is correct
20 Correct 252 ms 37460 KB Output is correct
21 Correct 243 ms 32836 KB Output is correct
22 Correct 210 ms 32780 KB Output is correct
23 Correct 236 ms 33268 KB Output is correct
24 Correct 228 ms 33336 KB Output is correct
25 Correct 248 ms 35020 KB Output is correct
26 Correct 230 ms 32596 KB Output is correct
27 Correct 217 ms 32716 KB Output is correct
28 Incorrect 138 ms 7764 KB Extra information in the output file
29 Halted 0 ms 0 KB -