oj.uz

Submission #1092107

# Submission time Handle Problem Language Result Execution time Memory
1092107 2024-09-23T08:03:18 Z simona1230 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 53244 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];
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

# Verdict Execution time Memory Grader output
1 Correct 149 ms 18000 KB Output is correct
2 Correct 440 ms 19412 KB Output is correct
3 Correct 418 ms 19540 KB Output is correct
4 Correct 445 ms 19528 KB Output is correct
5 Correct 446 ms 19680 KB Output is correct
6 Correct 465 ms 19540 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 149 ms 18000 KB Output is correct
2 Correct 440 ms 19412 KB Output is correct
3 Correct 418 ms 19540 KB Output is correct
4 Correct 445 ms 19528 KB Output is correct
5 Correct 446 ms 19680 KB Output is correct
6 Correct 465 ms 19540 KB Output is correct
7 Correct 141 ms 18300 KB Output is correct
8 Correct 451 ms 20052 KB Output is correct
9 Correct 450 ms 20048 KB Output is correct
10 Correct 474 ms 20136 KB Output is correct
11 Correct 460 ms 20564 KB Output is correct
12 Correct 432 ms 19920 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 141 ms 18180 KB Output is correct
2 Execution timed out 3524 ms 44480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 141 ms 18180 KB Output is correct
2 Execution timed out 3524 ms 44480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 18188 KB Output is correct
2 Execution timed out 3556 ms 53104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 18188 KB Output is correct
2 Execution timed out 3556 ms 53104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 17972 KB Output is correct
2 Execution timed out 3543 ms 44688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 17972 KB Output is correct
2 Execution timed out 3543 ms 44688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 140 ms 18064 KB Output is correct
2 Execution timed out 3545 ms 53244 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 140 ms 18064 KB Output is correct
2 Execution timed out 3545 ms 53244 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 139 ms 18000 KB Output is correct
2 Correct 457 ms 19280 KB Output is correct
3 Correct 434 ms 19540 KB Output is correct
4 Correct 466 ms 19468 KB Output is correct
5 Correct 454 ms 19688 KB Output is correct
6 Correct 427 ms 19536 KB Output is correct
7 Correct 143 ms 18200 KB Output is correct
8 Execution timed out 3568 ms 44588 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 139 ms 18000 KB Output is correct
2 Correct 457 ms 19280 KB Output is correct
3 Correct 434 ms 19540 KB Output is correct
4 Correct 466 ms 19468 KB Output is correct
5 Correct 454 ms 19688 KB Output is correct
6 Correct 427 ms 19536 KB Output is correct
7 Correct 143 ms 18200 KB Output is correct
8 Execution timed out 3568 ms 44588 KB Time limit exceeded
9 Halted 0 ms 0 KB -