oj.uz

Submission #1092108

# Submission time Handle Problem Language Result Execution time Memory
1092108 2024-09-23T08:05:21 Z simona1230 Inside information (BOI21_servers) C++17
100 / 100
 509 ms 54868 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;
}
vector<int> undo;
void incdfs(int i,int last,int p)
{
    undo.push_back(last);
    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)
{
    for(int i: undo)
        update(1,1,n+k,i,-1);
    undo.clear();
    //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 134 ms 14160 KB Output is correct
2 Correct 146 ms 15184 KB Output is correct
3 Correct 149 ms 15440 KB Output is correct
4 Correct 151 ms 15280 KB Output is correct
5 Correct 156 ms 14672 KB Output is correct
6 Correct 148 ms 14732 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 134 ms 14160 KB Output is correct
2 Correct 146 ms 15184 KB Output is correct
3 Correct 149 ms 15440 KB Output is correct
4 Correct 151 ms 15280 KB Output is correct
5 Correct 156 ms 14672 KB Output is correct
6 Correct 148 ms 14732 KB Output is correct
7 Correct 142 ms 14452 KB Output is correct
8 Correct 155 ms 16036 KB Output is correct
9 Correct 156 ms 16240 KB Output is correct
10 Correct 161 ms 16344 KB Output is correct
11 Correct 157 ms 15440 KB Output is correct
12 Correct 156 ms 15584 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 14164 KB Output is correct
2 Correct 231 ms 41408 KB Output is correct
3 Correct 233 ms 44228 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 14164 KB Output is correct
2 Correct 231 ms 41408 KB Output is correct
3 Correct 233 ms 44228 KB Output is correct
4 Correct 135 ms 15184 KB Output is correct
5 Correct 235 ms 45256 KB Output is correct
6 Correct 211 ms 44748 KB Output is correct
7 Correct 215 ms 44936 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13908 KB Output is correct
2 Correct 291 ms 49008 KB Output is correct
3 Correct 281 ms 52304 KB Output is correct
4 Correct 391 ms 52380 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13908 KB Output is correct
2 Correct 291 ms 49008 KB Output is correct
3 Correct 281 ms 52304 KB Output is correct
4 Correct 391 ms 52380 KB Output is correct
5 Correct 134 ms 15184 KB Output is correct
6 Correct 312 ms 54096 KB Output is correct
7 Correct 447 ms 54736 KB Output is correct
8 Correct 340 ms 54868 KB Output is correct
9 Correct 327 ms 54684 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 14164 KB Output is correct
2 Correct 360 ms 40236 KB Output is correct
3 Correct 282 ms 44116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 14164 KB Output is correct
2 Correct 360 ms 40236 KB Output is correct
3 Correct 282 ms 44116 KB Output is correct
4 Correct 135 ms 15188 KB Output is correct
5 Correct 440 ms 45748 KB Output is correct
6 Correct 301 ms 45904 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 14132 KB Output is correct
2 Correct 310 ms 48832 KB Output is correct
3 Correct 284 ms 52220 KB Output is correct
4 Correct 400 ms 52436 KB Output is correct
5 Correct 133 ms 14976 KB Output is correct
6 Correct 337 ms 43472 KB Output is correct
7 Correct 267 ms 44272 KB Output is correct
8 Correct 292 ms 43776 KB Output is correct
9 Correct 312 ms 44628 KB Output is correct
10 Correct 358 ms 49224 KB Output is correct
11 Correct 391 ms 47920 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 14132 KB Output is correct
2 Correct 310 ms 48832 KB Output is correct
3 Correct 284 ms 52220 KB Output is correct
4 Correct 400 ms 52436 KB Output is correct
5 Correct 133 ms 14976 KB Output is correct
6 Correct 337 ms 43472 KB Output is correct
7 Correct 267 ms 44272 KB Output is correct
8 Correct 292 ms 43776 KB Output is correct
9 Correct 312 ms 44628 KB Output is correct
10 Correct 358 ms 49224 KB Output is correct
11 Correct 391 ms 47920 KB Output is correct
12 Correct 145 ms 15244 KB Output is correct
13 Correct 353 ms 54188 KB Output is correct
14 Correct 502 ms 54736 KB Output is correct
15 Correct 367 ms 54608 KB Output is correct
16 Correct 338 ms 54612 KB Output is correct
17 Correct 152 ms 15184 KB Output is correct
18 Correct 419 ms 45648 KB Output is correct
19 Correct 292 ms 45904 KB Output is correct
20 Correct 300 ms 45692 KB Output is correct
21 Correct 306 ms 46640 KB Output is correct
22 Correct 483 ms 51024 KB Output is correct
23 Correct 502 ms 49784 KB Output is correct
24 Correct 437 ms 48628 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 14104 KB Output is correct
2 Correct 144 ms 15184 KB Output is correct
3 Correct 141 ms 15444 KB Output is correct
4 Correct 150 ms 15472 KB Output is correct
5 Correct 160 ms 14724 KB Output is correct
6 Correct 144 ms 14708 KB Output is correct
7 Correct 143 ms 14160 KB Output is correct
8 Correct 229 ms 41412 KB Output is correct
9 Correct 232 ms 44224 KB Output is correct
10 Correct 137 ms 14808 KB Output is correct
11 Correct 321 ms 52308 KB Output is correct
12 Correct 303 ms 52216 KB Output is correct
13 Correct 400 ms 52432 KB Output is correct
14 Correct 133 ms 14984 KB Output is correct
15 Correct 361 ms 43580 KB Output is correct
16 Correct 261 ms 44112 KB Output is correct
17 Correct 291 ms 43676 KB Output is correct
18 Correct 275 ms 44488 KB Output is correct
19 Correct 355 ms 49236 KB Output is correct
20 Correct 404 ms 47956 KB Output is correct
21 Correct 271 ms 44612 KB Output is correct
22 Correct 247 ms 44364 KB Output is correct
23 Correct 275 ms 44144 KB Output is correct
24 Correct 294 ms 44116 KB Output is correct
25 Correct 301 ms 48584 KB Output is correct
26 Correct 282 ms 43728 KB Output is correct
27 Correct 262 ms 43600 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 14104 KB Output is correct
2 Correct 144 ms 15184 KB Output is correct
3 Correct 141 ms 15444 KB Output is correct
4 Correct 150 ms 15472 KB Output is correct
5 Correct 160 ms 14724 KB Output is correct
6 Correct 144 ms 14708 KB Output is correct
7 Correct 143 ms 14160 KB Output is correct
8 Correct 229 ms 41412 KB Output is correct
9 Correct 232 ms 44224 KB Output is correct
10 Correct 137 ms 14808 KB Output is correct
11 Correct 321 ms 52308 KB Output is correct
12 Correct 303 ms 52216 KB Output is correct
13 Correct 400 ms 52432 KB Output is correct
14 Correct 133 ms 14984 KB Output is correct
15 Correct 361 ms 43580 KB Output is correct
16 Correct 261 ms 44112 KB Output is correct
17 Correct 291 ms 43676 KB Output is correct
18 Correct 275 ms 44488 KB Output is correct
19 Correct 355 ms 49236 KB Output is correct
20 Correct 404 ms 47956 KB Output is correct
21 Correct 271 ms 44612 KB Output is correct
22 Correct 247 ms 44364 KB Output is correct
23 Correct 275 ms 44144 KB Output is correct
24 Correct 294 ms 44116 KB Output is correct
25 Correct 301 ms 48584 KB Output is correct
26 Correct 282 ms 43728 KB Output is correct
27 Correct 262 ms 43600 KB Output is correct
28 Correct 140 ms 15084 KB Output is correct
29 Correct 163 ms 17232 KB Output is correct
30 Correct 152 ms 17288 KB Output is correct
31 Correct 164 ms 17236 KB Output is correct
32 Correct 168 ms 16468 KB Output is correct
33 Correct 151 ms 16720 KB Output is correct
34 Correct 160 ms 15168 KB Output is correct
35 Correct 258 ms 45512 KB Output is correct
36 Correct 226 ms 44760 KB Output is correct
37 Correct 239 ms 45000 KB Output is correct
38 Correct 146 ms 15308 KB Output is correct
39 Correct 307 ms 54100 KB Output is correct
40 Correct 459 ms 54736 KB Output is correct
41 Correct 320 ms 54700 KB Output is correct
42 Correct 322 ms 54468 KB Output is correct
43 Correct 135 ms 15188 KB Output is correct
44 Correct 413 ms 45516 KB Output is correct
45 Correct 317 ms 45904 KB Output is correct
46 Correct 346 ms 45780 KB Output is correct
47 Correct 315 ms 46676 KB Output is correct
48 Correct 509 ms 51120 KB Output is correct
49 Correct 504 ms 50000 KB Output is correct
50 Correct 435 ms 48796 KB Output is correct
51 Correct 266 ms 45640 KB Output is correct
52 Correct 247 ms 45704 KB Output is correct
53 Correct 224 ms 45252 KB Output is correct
54 Correct 223 ms 46080 KB Output is correct
55 Correct 233 ms 45264 KB Output is correct
56 Correct 267 ms 45140 KB Output is correct
57 Correct 289 ms 49424 KB Output is correct
58 Correct 349 ms 45656 KB Output is correct
59 Correct 276 ms 44436 KB Output is correct