oj.uz

Submission #1091967

# Submission time Handle Problem Language Result Execution time Memory
1091967 2024-09-22T17:50:05 Z simona1230 Inside information (BOI21_servers) C++17
52.5 / 100
 374 ms 44664 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]);
            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

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8784 KB Output is correct
2 Correct 140 ms 10076 KB Output is correct
3 Correct 139 ms 10072 KB Output is correct
4 Correct 145 ms 10064 KB Output is correct
5 Correct 167 ms 10348 KB Output is correct
6 Correct 142 ms 10068 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8784 KB Output is correct
2 Correct 140 ms 10076 KB Output is correct
3 Correct 139 ms 10072 KB Output is correct
4 Correct 145 ms 10064 KB Output is correct
5 Correct 167 ms 10348 KB Output is correct
6 Correct 142 ms 10068 KB Output is correct
7 Incorrect 140 ms 8528 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 142 ms 8672 KB Output is correct
2 Correct 221 ms 35528 KB Output is correct
3 Correct 208 ms 35668 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 8672 KB Output is correct
2 Correct 221 ms 35528 KB Output is correct
3 Correct 208 ms 35668 KB Output is correct
4 Correct 169 ms 8716 KB Output is correct
5 Correct 219 ms 35472 KB Output is correct
6 Correct 228 ms 34688 KB Output is correct
7 Correct 196 ms 35012 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 8784 KB Output is correct
2 Correct 283 ms 44536 KB Output is correct
3 Correct 233 ms 44500 KB Output is correct
4 Correct 217 ms 44624 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 8784 KB Output is correct
2 Correct 283 ms 44536 KB Output is correct
3 Correct 233 ms 44500 KB Output is correct
4 Correct 217 ms 44624 KB Output is correct
5 Incorrect 131 ms 8528 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 132 ms 8784 KB Output is correct
2 Correct 235 ms 36164 KB Output is correct
3 Correct 261 ms 36476 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 8784 KB Output is correct
2 Correct 235 ms 36164 KB Output is correct
3 Correct 261 ms 36476 KB Output is correct
4 Incorrect 138 ms 8532 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 135 ms 8624 KB Output is correct
2 Correct 260 ms 44520 KB Output is correct
3 Correct 274 ms 44524 KB Output is correct
4 Correct 227 ms 44372 KB Output is correct
5 Correct 134 ms 8720 KB Output is correct
6 Correct 200 ms 35924 KB Output is correct
7 Correct 226 ms 36612 KB Output is correct
8 Correct 254 ms 36944 KB Output is correct
9 Correct 234 ms 36948 KB Output is correct
10 Correct 272 ms 41624 KB Output is correct
11 Correct 265 ms 40784 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 8624 KB Output is correct
2 Correct 260 ms 44520 KB Output is correct
3 Correct 274 ms 44524 KB Output is correct
4 Correct 227 ms 44372 KB Output is correct
5 Correct 134 ms 8720 KB Output is correct
6 Correct 200 ms 35924 KB Output is correct
7 Correct 226 ms 36612 KB Output is correct
8 Correct 254 ms 36944 KB Output is correct
9 Correct 234 ms 36948 KB Output is correct
10 Correct 272 ms 41624 KB Output is correct
11 Correct 265 ms 40784 KB Output is correct
12 Incorrect 138 ms 8532 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 167 ms 8784 KB Output is correct
2 Correct 143 ms 10328 KB Output is correct
3 Correct 139 ms 10052 KB Output is correct
4 Correct 150 ms 10064 KB Output is correct
5 Correct 159 ms 10364 KB Output is correct
6 Correct 139 ms 10064 KB Output is correct
7 Correct 131 ms 8764 KB Output is correct
8 Correct 236 ms 35528 KB Output is correct
9 Correct 238 ms 35780 KB Output is correct
10 Correct 169 ms 8764 KB Output is correct
11 Correct 277 ms 44664 KB Output is correct
12 Correct 336 ms 44624 KB Output is correct
13 Correct 268 ms 44372 KB Output is correct
14 Correct 186 ms 8564 KB Output is correct
15 Correct 266 ms 35944 KB Output is correct
16 Correct 287 ms 36512 KB Output is correct
17 Correct 344 ms 36948 KB Output is correct
18 Correct 357 ms 37028 KB Output is correct
19 Correct 344 ms 41388 KB Output is correct
20 Correct 374 ms 40668 KB Output is correct
21 Correct 262 ms 36136 KB Output is correct
22 Correct 274 ms 36276 KB Output is correct
23 Correct 269 ms 36432 KB Output is correct
24 Correct 281 ms 36704 KB Output is correct
25 Correct 320 ms 38292 KB Output is correct
26 Correct 275 ms 35916 KB Output is correct
27 Correct 320 ms 36072 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 167 ms 8784 KB Output is correct
2 Correct 143 ms 10328 KB Output is correct
3 Correct 139 ms 10052 KB Output is correct
4 Correct 150 ms 10064 KB Output is correct
5 Correct 159 ms 10364 KB Output is correct
6 Correct 139 ms 10064 KB Output is correct
7 Correct 131 ms 8764 KB Output is correct
8 Correct 236 ms 35528 KB Output is correct
9 Correct 238 ms 35780 KB Output is correct
10 Correct 169 ms 8764 KB Output is correct
11 Correct 277 ms 44664 KB Output is correct
12 Correct 336 ms 44624 KB Output is correct
13 Correct 268 ms 44372 KB Output is correct
14 Correct 186 ms 8564 KB Output is correct
15 Correct 266 ms 35944 KB Output is correct
16 Correct 287 ms 36512 KB Output is correct
17 Correct 344 ms 36948 KB Output is correct
18 Correct 357 ms 37028 KB Output is correct
19 Correct 344 ms 41388 KB Output is correct
20 Correct 374 ms 40668 KB Output is correct
21 Correct 262 ms 36136 KB Output is correct
22 Correct 274 ms 36276 KB Output is correct
23 Correct 269 ms 36432 KB Output is correct
24 Correct 281 ms 36704 KB Output is correct
25 Correct 320 ms 38292 KB Output is correct
26 Correct 275 ms 35916 KB Output is correct
27 Correct 320 ms 36072 KB Output is correct
28 Incorrect 141 ms 8560 KB Extra information in the output file
29 Halted 0 ms 0 KB -