oj.uz

Submission #1091946

# Submission time Handle Problem Language Result Execution time Memory
1091946 2024-09-22T17:03:24 Z simona1230 Inside information (BOI21_servers) C++17
52.5 / 100
 274 ms 44688 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);
            }
        }
        if(a[i].c=='Q')cout<<typeQ(i,a[i].x,a[i].y)<<endl;
        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 144 ms 8788 KB Output is correct
2 Correct 143 ms 10020 KB Output is correct
3 Correct 144 ms 10068 KB Output is correct
4 Correct 149 ms 10188 KB Output is correct
5 Correct 146 ms 10320 KB Output is correct
6 Correct 146 ms 10048 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8788 KB Output is correct
2 Correct 143 ms 10020 KB Output is correct
3 Correct 144 ms 10068 KB Output is correct
4 Correct 149 ms 10188 KB Output is correct
5 Correct 146 ms 10320 KB Output is correct
6 Correct 146 ms 10048 KB Output is correct
7 Incorrect 135 ms 8788 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 136 ms 8784 KB Output is correct
2 Correct 211 ms 35780 KB Output is correct
3 Correct 218 ms 35520 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 136 ms 8784 KB Output is correct
2 Correct 211 ms 35780 KB Output is correct
3 Correct 218 ms 35520 KB Output is correct
4 Correct 137 ms 8764 KB Output is correct
5 Correct 226 ms 35524 KB Output is correct
6 Correct 208 ms 34760 KB Output is correct
7 Correct 212 ms 34920 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8784 KB Output is correct
2 Correct 251 ms 44628 KB Output is correct
3 Correct 263 ms 44676 KB Output is correct
4 Correct 232 ms 44628 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8784 KB Output is correct
2 Correct 251 ms 44628 KB Output is correct
3 Correct 263 ms 44676 KB Output is correct
4 Correct 232 ms 44628 KB Output is correct
5 Incorrect 136 ms 8728 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 170 ms 8748 KB Output is correct
2 Correct 226 ms 36164 KB Output is correct
3 Correct 248 ms 36600 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 8748 KB Output is correct
2 Correct 226 ms 36164 KB Output is correct
3 Correct 248 ms 36600 KB Output is correct
4 Incorrect 136 ms 8528 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 134 ms 8788 KB Output is correct
2 Correct 245 ms 44540 KB Output is correct
3 Correct 248 ms 44624 KB Output is correct
4 Correct 227 ms 44372 KB Output is correct
5 Correct 132 ms 8788 KB Output is correct
6 Correct 216 ms 36176 KB Output is correct
7 Correct 243 ms 36680 KB Output is correct
8 Correct 271 ms 36944 KB Output is correct
9 Correct 258 ms 36944 KB Output is correct
10 Correct 246 ms 41552 KB Output is correct
11 Correct 274 ms 40856 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8788 KB Output is correct
2 Correct 245 ms 44540 KB Output is correct
3 Correct 248 ms 44624 KB Output is correct
4 Correct 227 ms 44372 KB Output is correct
5 Correct 132 ms 8788 KB Output is correct
6 Correct 216 ms 36176 KB Output is correct
7 Correct 243 ms 36680 KB Output is correct
8 Correct 271 ms 36944 KB Output is correct
9 Correct 258 ms 36944 KB Output is correct
10 Correct 246 ms 41552 KB Output is correct
11 Correct 274 ms 40856 KB Output is correct
12 Incorrect 146 ms 8724 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 138 ms 8548 KB Output is correct
2 Correct 145 ms 10052 KB Output is correct
3 Correct 142 ms 10084 KB Output is correct
4 Correct 153 ms 10368 KB Output is correct
5 Correct 152 ms 10376 KB Output is correct
6 Correct 145 ms 10068 KB Output is correct
7 Correct 144 ms 8784 KB Output is correct
8 Correct 221 ms 35704 KB Output is correct
9 Correct 232 ms 35604 KB Output is correct
10 Correct 138 ms 8784 KB Output is correct
11 Correct 253 ms 44688 KB Output is correct
12 Correct 256 ms 44676 KB Output is correct
13 Correct 229 ms 44496 KB Output is correct
14 Correct 132 ms 8788 KB Output is correct
15 Correct 215 ms 35980 KB Output is correct
16 Correct 235 ms 36484 KB Output is correct
17 Correct 248 ms 36964 KB Output is correct
18 Correct 239 ms 36948 KB Output is correct
19 Correct 225 ms 41408 KB Output is correct
20 Correct 245 ms 40784 KB Output is correct
21 Correct 218 ms 36160 KB Output is correct
22 Correct 218 ms 36092 KB Output is correct
23 Correct 234 ms 36352 KB Output is correct
24 Correct 232 ms 36692 KB Output is correct
25 Correct 223 ms 38340 KB Output is correct
26 Correct 220 ms 36080 KB Output is correct
27 Correct 220 ms 36180 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 138 ms 8548 KB Output is correct
2 Correct 145 ms 10052 KB Output is correct
3 Correct 142 ms 10084 KB Output is correct
4 Correct 153 ms 10368 KB Output is correct
5 Correct 152 ms 10376 KB Output is correct
6 Correct 145 ms 10068 KB Output is correct
7 Correct 144 ms 8784 KB Output is correct
8 Correct 221 ms 35704 KB Output is correct
9 Correct 232 ms 35604 KB Output is correct
10 Correct 138 ms 8784 KB Output is correct
11 Correct 253 ms 44688 KB Output is correct
12 Correct 256 ms 44676 KB Output is correct
13 Correct 229 ms 44496 KB Output is correct
14 Correct 132 ms 8788 KB Output is correct
15 Correct 215 ms 35980 KB Output is correct
16 Correct 235 ms 36484 KB Output is correct
17 Correct 248 ms 36964 KB Output is correct
18 Correct 239 ms 36948 KB Output is correct
19 Correct 225 ms 41408 KB Output is correct
20 Correct 245 ms 40784 KB Output is correct
21 Correct 218 ms 36160 KB Output is correct
22 Correct 218 ms 36092 KB Output is correct
23 Correct 234 ms 36352 KB Output is correct
24 Correct 232 ms 36692 KB Output is correct
25 Correct 223 ms 38340 KB Output is correct
26 Correct 220 ms 36080 KB Output is correct
27 Correct 220 ms 36180 KB Output is correct
28 Incorrect 133 ms 8556 KB Extra information in the output file
29 Halted 0 ms 0 KB -