oj.uz

Submission #1091582

# Submission time Handle Problem Language Result Execution time Memory
1091582 2024-09-21T12:31:53 Z simona1230 Inside information (BOI21_servers) C++17
50 / 100
 265 ms 43688 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 t,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]=++t;

    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]=t;
}

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";
}

void solve()
{
    for(int i=1;i<=n+k-1;i++)
    {
        if(a[i].c=='Q')cout<<typeQ(i,a[i].x,a[i].y)<<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 135 ms 7844 KB Output is correct
2 Correct 139 ms 10064 KB Output is correct
3 Correct 138 ms 10068 KB Output is correct
4 Correct 153 ms 10120 KB Output is correct
5 Correct 150 ms 10320 KB Output is correct
6 Correct 153 ms 10116 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 7844 KB Output is correct
2 Correct 139 ms 10064 KB Output is correct
3 Correct 138 ms 10068 KB Output is correct
4 Correct 153 ms 10120 KB Output is correct
5 Correct 150 ms 10320 KB Output is correct
6 Correct 153 ms 10116 KB Output is correct
7 Incorrect 138 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 147 ms 7764 KB Output is correct
2 Correct 216 ms 34500 KB Output is correct
3 Correct 226 ms 34500 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 147 ms 7764 KB Output is correct
2 Correct 216 ms 34500 KB Output is correct
3 Correct 226 ms 34500 KB Output is correct
4 Incorrect 141 ms 8752 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 133 ms 7764 KB Output is correct
2 Correct 212 ms 43600 KB Output is correct
3 Correct 208 ms 43600 KB Output is correct
4 Correct 215 ms 43688 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 7764 KB Output is correct
2 Correct 212 ms 43600 KB Output is correct
3 Correct 208 ms 43600 KB Output is correct
4 Correct 215 ms 43688 KB Output is correct
5 Incorrect 127 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 146 ms 7764 KB Output is correct
2 Correct 211 ms 35040 KB Output is correct
3 Correct 219 ms 35412 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 7764 KB Output is correct
2 Correct 211 ms 35040 KB Output is correct
3 Correct 219 ms 35412 KB Output is correct
4 Incorrect 130 ms 8796 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 152 ms 7804 KB Output is correct
2 Correct 202 ms 43604 KB Output is correct
3 Correct 207 ms 43604 KB Output is correct
4 Correct 223 ms 43348 KB Output is correct
5 Correct 133 ms 8788 KB Output is correct
6 Correct 210 ms 34900 KB Output is correct
7 Correct 201 ms 35408 KB Output is correct
8 Correct 226 ms 35988 KB Output is correct
9 Correct 212 ms 35964 KB Output is correct
10 Correct 207 ms 40532 KB Output is correct
11 Correct 223 ms 39632 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 7804 KB Output is correct
2 Correct 202 ms 43604 KB Output is correct
3 Correct 207 ms 43604 KB Output is correct
4 Correct 223 ms 43348 KB Output is correct
5 Correct 133 ms 8788 KB Output is correct
6 Correct 210 ms 34900 KB Output is correct
7 Correct 201 ms 35408 KB Output is correct
8 Correct 226 ms 35988 KB Output is correct
9 Correct 212 ms 35964 KB Output is correct
10 Correct 207 ms 40532 KB Output is correct
11 Correct 223 ms 39632 KB Output is correct
12 Incorrect 126 ms 8704 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 142 ms 7716 KB Output is correct
2 Correct 142 ms 10064 KB Output is correct
3 Correct 151 ms 10064 KB Output is correct
4 Correct 162 ms 10112 KB Output is correct
5 Correct 145 ms 10304 KB Output is correct
6 Correct 141 ms 9980 KB Output is correct
7 Correct 145 ms 8812 KB Output is correct
8 Correct 207 ms 34596 KB Output is correct
9 Correct 218 ms 34496 KB Output is correct
10 Correct 137 ms 8544 KB Output is correct
11 Correct 205 ms 43484 KB Output is correct
12 Correct 235 ms 43480 KB Output is correct
13 Correct 265 ms 43348 KB Output is correct
14 Correct 134 ms 8652 KB Output is correct
15 Correct 188 ms 35084 KB Output is correct
16 Correct 200 ms 35416 KB Output is correct
17 Correct 218 ms 35948 KB Output is correct
18 Correct 204 ms 35920 KB Output is correct
19 Correct 208 ms 40400 KB Output is correct
20 Correct 243 ms 39800 KB Output is correct
21 Correct 195 ms 35136 KB Output is correct
22 Correct 205 ms 35252 KB Output is correct
23 Correct 218 ms 35412 KB Output is correct
24 Correct 213 ms 35420 KB Output is correct
25 Correct 194 ms 37324 KB Output is correct
26 Correct 208 ms 34896 KB Output is correct
27 Correct 197 ms 34900 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 7716 KB Output is correct
2 Correct 142 ms 10064 KB Output is correct
3 Correct 151 ms 10064 KB Output is correct
4 Correct 162 ms 10112 KB Output is correct
5 Correct 145 ms 10304 KB Output is correct
6 Correct 141 ms 9980 KB Output is correct
7 Correct 145 ms 8812 KB Output is correct
8 Correct 207 ms 34596 KB Output is correct
9 Correct 218 ms 34496 KB Output is correct
10 Correct 137 ms 8544 KB Output is correct
11 Correct 205 ms 43484 KB Output is correct
12 Correct 235 ms 43480 KB Output is correct
13 Correct 265 ms 43348 KB Output is correct
14 Correct 134 ms 8652 KB Output is correct
15 Correct 188 ms 35084 KB Output is correct
16 Correct 200 ms 35416 KB Output is correct
17 Correct 218 ms 35948 KB Output is correct
18 Correct 204 ms 35920 KB Output is correct
19 Correct 208 ms 40400 KB Output is correct
20 Correct 243 ms 39800 KB Output is correct
21 Correct 195 ms 35136 KB Output is correct
22 Correct 205 ms 35252 KB Output is correct
23 Correct 218 ms 35412 KB Output is correct
24 Correct 213 ms 35420 KB Output is correct
25 Correct 194 ms 37324 KB Output is correct
26 Correct 208 ms 34896 KB Output is correct
27 Correct 197 ms 34900 KB Output is correct
28 Incorrect 129 ms 8532 KB Extra information in the output file
29 Halted 0 ms 0 KB -