oj.uz

Submission #1092093

# Submission time Handle Problem Language Result Execution time Memory
1092093 2024-09-23T07:04:49 Z simona1230 Inside information (BOI21_servers) C++17
50 / 100
 280 ms 45268 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);
}

int f[maxn];

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);
            f[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=2;
            if(x==1)rem=0;
            else if(jump[x][0]==1)rem=1;
            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 134 ms 8788 KB Output is correct
2 Correct 142 ms 10136 KB Output is correct
3 Correct 140 ms 10128 KB Output is correct
4 Correct 150 ms 10032 KB Output is correct
5 Correct 145 ms 10324 KB Output is correct
6 Correct 141 ms 10148 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8788 KB Output is correct
2 Correct 142 ms 10136 KB Output is correct
3 Correct 140 ms 10128 KB Output is correct
4 Correct 150 ms 10032 KB Output is correct
5 Correct 145 ms 10324 KB Output is correct
6 Correct 141 ms 10148 KB Output is correct
7 Incorrect 135 ms 8532 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 144 ms 8832 KB Output is correct
2 Correct 217 ms 36184 KB Output is correct
3 Correct 250 ms 36040 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8832 KB Output is correct
2 Correct 217 ms 36184 KB Output is correct
3 Correct 250 ms 36040 KB Output is correct
4 Incorrect 138 ms 8784 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 8788 KB Output is correct
2 Correct 253 ms 45140 KB Output is correct
3 Correct 240 ms 45048 KB Output is correct
4 Correct 220 ms 44972 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 8788 KB Output is correct
2 Correct 253 ms 45140 KB Output is correct
3 Correct 240 ms 45048 KB Output is correct
4 Correct 220 ms 44972 KB Output is correct
5 Incorrect 148 ms 8776 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 134 ms 8784 KB Output is correct
2 Correct 216 ms 36432 KB Output is correct
3 Correct 245 ms 36948 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8784 KB Output is correct
2 Correct 216 ms 36432 KB Output is correct
3 Correct 245 ms 36948 KB Output is correct
4 Incorrect 132 ms 8768 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 8804 KB Output is correct
2 Correct 241 ms 45268 KB Output is correct
3 Correct 229 ms 45136 KB Output is correct
4 Correct 214 ms 44884 KB Output is correct
5 Correct 133 ms 8784 KB Output is correct
6 Correct 198 ms 36432 KB Output is correct
7 Correct 232 ms 36944 KB Output is correct
8 Correct 265 ms 37456 KB Output is correct
9 Correct 264 ms 37460 KB Output is correct
10 Correct 240 ms 42064 KB Output is correct
11 Correct 280 ms 41368 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8804 KB Output is correct
2 Correct 241 ms 45268 KB Output is correct
3 Correct 229 ms 45136 KB Output is correct
4 Correct 214 ms 44884 KB Output is correct
5 Correct 133 ms 8784 KB Output is correct
6 Correct 198 ms 36432 KB Output is correct
7 Correct 232 ms 36944 KB Output is correct
8 Correct 265 ms 37456 KB Output is correct
9 Correct 264 ms 37460 KB Output is correct
10 Correct 240 ms 42064 KB Output is correct
11 Correct 280 ms 41368 KB Output is correct
12 Incorrect 152 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 140 ms 8788 KB Output is correct
2 Correct 146 ms 10068 KB Output is correct
3 Correct 158 ms 10324 KB Output is correct
4 Correct 151 ms 10184 KB Output is correct
5 Correct 145 ms 10320 KB Output is correct
6 Correct 141 ms 10064 KB Output is correct
7 Correct 137 ms 8704 KB Output is correct
8 Correct 214 ms 36044 KB Output is correct
9 Correct 207 ms 36136 KB Output is correct
10 Correct 132 ms 8784 KB Output is correct
11 Correct 226 ms 45016 KB Output is correct
12 Correct 235 ms 45048 KB Output is correct
13 Correct 207 ms 45068 KB Output is correct
14 Correct 147 ms 8760 KB Output is correct
15 Correct 212 ms 36608 KB Output is correct
16 Correct 223 ms 36944 KB Output is correct
17 Correct 241 ms 37456 KB Output is correct
18 Correct 261 ms 37460 KB Output is correct
19 Correct 238 ms 42068 KB Output is correct
20 Correct 265 ms 41140 KB Output is correct
21 Correct 218 ms 36672 KB Output is correct
22 Correct 223 ms 36792 KB Output is correct
23 Correct 241 ms 36944 KB Output is correct
24 Correct 238 ms 37024 KB Output is correct
25 Correct 249 ms 38876 KB Output is correct
26 Correct 228 ms 36432 KB Output is correct
27 Correct 228 ms 36528 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8788 KB Output is correct
2 Correct 146 ms 10068 KB Output is correct
3 Correct 158 ms 10324 KB Output is correct
4 Correct 151 ms 10184 KB Output is correct
5 Correct 145 ms 10320 KB Output is correct
6 Correct 141 ms 10064 KB Output is correct
7 Correct 137 ms 8704 KB Output is correct
8 Correct 214 ms 36044 KB Output is correct
9 Correct 207 ms 36136 KB Output is correct
10 Correct 132 ms 8784 KB Output is correct
11 Correct 226 ms 45016 KB Output is correct
12 Correct 235 ms 45048 KB Output is correct
13 Correct 207 ms 45068 KB Output is correct
14 Correct 147 ms 8760 KB Output is correct
15 Correct 212 ms 36608 KB Output is correct
16 Correct 223 ms 36944 KB Output is correct
17 Correct 241 ms 37456 KB Output is correct
18 Correct 261 ms 37460 KB Output is correct
19 Correct 238 ms 42068 KB Output is correct
20 Correct 265 ms 41140 KB Output is correct
21 Correct 218 ms 36672 KB Output is correct
22 Correct 223 ms 36792 KB Output is correct
23 Correct 241 ms 36944 KB Output is correct
24 Correct 238 ms 37024 KB Output is correct
25 Correct 249 ms 38876 KB Output is correct
26 Correct 228 ms 36432 KB Output is correct
27 Correct 228 ms 36528 KB Output is correct
28 Incorrect 136 ms 8716 KB Extra information in the output file
29 Halted 0 ms 0 KB -