oj.uz

Submission #904062

# Submission time Handle Problem Language Result Execution time Memory
904062 2024-01-11T19:15:44 Z simona1230 Inside information (BOI21_servers) C++17
30 / 100
 1814 ms 67468 KB 
#include <bits/stdc++.h>

using namespace std;

int n,k;
int in[4001][4001];
char C[240001];
int X[240001],Y[240001];
bool sbt2=1,sbt3=1;
void read()
{
    cin>>n>>k;
    for(int i=1; i<=n+k-1; i++)
    {
        cin>>C[i]>>X[i];
        if(C[i]!='C')cin>>Y[i];
        if(C[i]=='S'&&min(X[i],Y[i])!=1)sbt2=0;
        if(C[i]=='S'&&abs(X[i]-Y[i])!=1)sbt3=0;
    }
}
void slow()
{
    for(int i=1; i<=n; i++)
        in[i][i]=1;
    for(int i=1; i<=n+k-1; i++)
    {
        int x,y;
        char c;
        x=X[i];
        y=Y[i];
        c=C[i];
        if(c=='S')
        {
            for(int j=1; j<=n; j++)
            {
                in[x][j]=in[y][j]=max(in[x][j],in[y][j]);
            }
        }
        if(c=='C')
        {
            int cnt=0;
            for(int j=1; j<=n; j++)
                cnt+=in[j][x];
            cout<<cnt<<endl;
        }
        if(c=='Q')
        {
            if(in[x][y])cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }
    }
}


int t[120001];
void subt2()
{
    t[1]=1;
    int sec=2;
    for(int i=1; i<=n+k-1; i++)
    {
        int x,y;
        char c;
        x=X[i];
        y=Y[i];
        c=C[i];
        if(c=='S')
        {
            t[max(x,y)]=sec++;
        }

        if(c=='Q')
        {
            if(t[y]&&t[y]<=t[x]||x==1&&t[y]||y==1&&t[x]||x==y)cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }

        if(c=='C')
        {
            if(t[x]==0)cout<<1<<endl;
            else if(x==1)cout<<sec-1<<endl;
            else cout<<sec-t[x]+1<<endl;
        }
    }
}

int inc[120001],de[120001];
int find_inc(int ver)
{
    if(ver==inc[ver])return ver;
    return inc[ver]=find_inc(inc[ver]);
}
int find_de(int ver)
{
    if(ver==de[ver])return ver;
    return de[ver]=find_de(de[ver]);
}

void subt3()
{
    int sec=1;
    for(int i=1; i<=n+k-1; i++)
    {
        int x,y;
        char c;
        x=X[i];
        y=Y[i];
        c=C[i];
        if(c=='S')
        {
            if(y<x)swap(x,y);
            t[x]=sec++;
            inc[x]=de[x]=x;
            if(t[x-1])inc[x-1]=x;
            if(t[x+1])de[x+1]=x;
        }
        if(c=='Q')
        {
            swap(x,y);
            int ver=x;
            if(y>x)
            {
                if(!t[ver])
                {
                    cout<<"no"<<endl;
                    continue;
                }
                ver=find_inc(ver);
                if(ver+1>=y)cout<<"yes"<<endl;
                else cout<<"no"<<endl;
            }
            else if(x>y)
            {
                if(!t[ver-1])
                {
                    cout<<"no"<<endl;
                    continue;
                }
                ver=find_de(ver-1);
                if(ver<=y)cout<<"yes"<<endl;
                else cout<<"no"<<endl;
            }
            else cout<<"yes"<<endl;
        }
        if(c=='C')
        {
            int cnt=1;
            /*for(int j=1;j<n;j++)
                cout<<inc[j]<<" ";
            cout<<endl;*/
            if(x!=n&&t[x])
            {
                //cout<<"! "<<x<<endl;
                cnt+=find_inc(x)-x+1;
            }
            if(x!=1&&t[x-1])
            {
                //cout<<"!! "<<x-1<<endl;
                cnt+=x-find_de(x-1);
            }
            cout<<cnt<<endl;
        }
    }
}

int cnt[1000001];
int p[1000001];
int used[1000001];
int val[1000001];

void subt4()
{
    for(int i=1; i<=n; i++)
        cnt[i]=1;
    int sec=1;
    for(int i=1; i<=n+k-1; i++)
    {
        //cout<<i<<": "<<endl;
        int x=X[i],y=Y[i];
        char c=C[i];
        if(c=='S')
        {
            int ver=max(x,y);
            p[ver]=min(x,y);
            t[ver]=sec++;
            int last=sec;
            while(p[ver]&&t[ver]<last&&t[ver])
            {
                last=t[ver];
                ver=p[ver];
                //cout<<ver<<" "<<cnt[max(x,y)]<<endl;
                cnt[ver]+=cnt[max(x,y)];
            }
        }
        if(c=='C')
        {
            int curr=cnt[x],ver=x,last=0;
            if(t[x])curr--;
            if(t[x]&&t[x*2]&&t[x*2]>t[x])curr-=cnt[x*2];
            if(t[x]&&t[x*2+1]&&t[x*2+1]>t[x])curr-=cnt[x*2+1];
            while(p[ver]&&t[ver]>last&&t[ver])
            {
                last=t[ver];
                ver=p[ver];
                //cout<<ver<<" - "<<cnt[ver]<<endl;
                curr+=cnt[ver];
            }
            cout<<curr<<endl;
        }
        if(c=='Q')
        {
            if(x==y)
            {
                cout<<"yes"<<endl;
                continue;
            }
            int ver=y,last=0;
            bool pos=0;
            //cout<<y<<" - ";
            while(p[ver]&&t[ver]>last&&t[ver])
            {
                last=t[ver];
                ver=p[ver];
                used[ver]=i;
                val[ver]=last;
                //cout<<ver<<" ";
                if(ver==x)pos=1;
            }
            //cout<<endl;

            //cout<<x<<" * ";

            ver=x,last=sec;
            while(p[ver]&&t[ver]<last&&t[ver])
            {
                last=t[ver];
                ver=p[ver];
                //cout<<ver<<" ";
                if(used[ver]==i&&last>val[ver]||ver==y)
                    pos=1;
            }
            //cout<<endl;

            if(pos)cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    read();
    if(n<=4000)slow();
    else if(sbt2)subt2();
    else if(sbt3)subt3();
    else subt4();
    return 0;
}
/*
15 0
S 1 2
S 1 3
S 2 4
S 5 10
S 2 5
Q 2 3
Q 3 2
Q 5 1
Q 1 5
Q 10 1
Q 11 11
Q 4 5
Q 4 1
Q 4 3
*/

Compilation message

servers.cpp: In function 'void subt2()':
servers.cpp:74:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   74 |             if(t[y]&&t[y]<=t[x]||x==1&&t[y]||y==1&&t[x]||x==y)cout<<"yes"<<endl;
      |                ~~~~^~~~~~~~~~~~
servers.cpp:74:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   74 |             if(t[y]&&t[y]<=t[x]||x==1&&t[y]||y==1&&t[x]||x==y)cout<<"yes"<<endl;
      |                                              ~~~~^~~~~~
servers.cpp: In function 'void subt4()':
servers.cpp:239:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  239 |                 if(used[ver]==i&&last>val[ver]||ver==y)
      |                    ~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 157 ms 5728 KB Output is correct
2 Correct 189 ms 67280 KB Output is correct
3 Correct 191 ms 67216 KB Output is correct
4 Correct 185 ms 67280 KB Output is correct
5 Correct 190 ms 67424 KB Output is correct
6 Correct 182 ms 67468 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 157 ms 5728 KB Output is correct
2 Correct 189 ms 67280 KB Output is correct
3 Correct 191 ms 67216 KB Output is correct
4 Correct 185 ms 67280 KB Output is correct
5 Correct 190 ms 67424 KB Output is correct
6 Correct 182 ms 67468 KB Output is correct
7 Correct 139 ms 5772 KB Output is correct
8 Correct 1814 ms 66964 KB Output is correct
9 Correct 538 ms 67156 KB Output is correct
10 Correct 1702 ms 67344 KB Output is correct
11 Correct 1720 ms 67428 KB Output is correct
12 Correct 459 ms 67168 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 146 ms 5716 KB Output is correct
2 Correct 184 ms 7764 KB Output is correct
3 Correct 161 ms 7768 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 146 ms 5716 KB Output is correct
2 Correct 184 ms 7764 KB Output is correct
3 Correct 161 ms 7768 KB Output is correct
4 Correct 191 ms 5672 KB Output is correct
5 Correct 166 ms 7484 KB Output is correct
6 Correct 153 ms 6812 KB Output is correct
7 Correct 157 ms 6820 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 5728 KB Output is correct
2 Correct 204 ms 9816 KB Output is correct
3 Correct 176 ms 10332 KB Output is correct
4 Correct 163 ms 10080 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 5728 KB Output is correct
2 Correct 204 ms 9816 KB Output is correct
3 Correct 176 ms 10332 KB Output is correct
4 Correct 163 ms 10080 KB Output is correct
5 Correct 152 ms 5696 KB Output is correct
6 Correct 165 ms 9788 KB Output is correct
7 Correct 172 ms 9876 KB Output is correct
8 Correct 164 ms 9264 KB Output is correct
9 Correct 158 ms 9300 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 5716 KB Output is correct
2 Correct 182 ms 16496 KB Output is correct
3 Correct 173 ms 16584 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 5716 KB Output is correct
2 Correct 182 ms 16496 KB Output is correct
3 Correct 173 ms 16584 KB Output is correct
4 Correct 140 ms 5728 KB Output is correct
5 Incorrect 175 ms 16288 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5704 KB Output is correct
2 Correct 182 ms 9824 KB Output is correct
3 Correct 171 ms 10300 KB Output is correct
4 Correct 172 ms 10192 KB Output is correct
5 Correct 139 ms 5792 KB Output is correct
6 Correct 227 ms 16576 KB Output is correct
7 Correct 195 ms 16760 KB Output is correct
8 Incorrect 168 ms 16432 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5704 KB Output is correct
2 Correct 182 ms 9824 KB Output is correct
3 Correct 171 ms 10300 KB Output is correct
4 Correct 172 ms 10192 KB Output is correct
5 Correct 139 ms 5792 KB Output is correct
6 Correct 227 ms 16576 KB Output is correct
7 Correct 195 ms 16760 KB Output is correct
8 Incorrect 168 ms 16432 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5768 KB Output is correct
2 Correct 200 ms 67324 KB Output is correct
3 Correct 179 ms 67380 KB Output is correct
4 Correct 202 ms 67412 KB Output is correct
5 Correct 178 ms 67412 KB Output is correct
6 Correct 182 ms 67180 KB Output is correct
7 Correct 174 ms 5820 KB Output is correct
8 Correct 181 ms 7776 KB Output is correct
9 Correct 221 ms 7872 KB Output is correct
10 Correct 157 ms 5800 KB Output is correct
11 Correct 164 ms 10324 KB Output is correct
12 Correct 187 ms 10212 KB Output is correct
13 Correct 206 ms 10172 KB Output is correct
14 Correct 150 ms 5716 KB Output is correct
15 Correct 188 ms 16748 KB Output is correct
16 Correct 218 ms 16636 KB Output is correct
17 Incorrect 168 ms 16592 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5768 KB Output is correct
2 Correct 200 ms 67324 KB Output is correct
3 Correct 179 ms 67380 KB Output is correct
4 Correct 202 ms 67412 KB Output is correct
5 Correct 178 ms 67412 KB Output is correct
6 Correct 182 ms 67180 KB Output is correct
7 Correct 174 ms 5820 KB Output is correct
8 Correct 181 ms 7776 KB Output is correct
9 Correct 221 ms 7872 KB Output is correct
10 Correct 157 ms 5800 KB Output is correct
11 Correct 164 ms 10324 KB Output is correct
12 Correct 187 ms 10212 KB Output is correct
13 Correct 206 ms 10172 KB Output is correct
14 Correct 150 ms 5716 KB Output is correct
15 Correct 188 ms 16748 KB Output is correct
16 Correct 218 ms 16636 KB Output is correct
17 Incorrect 168 ms 16592 KB Output isn't correct
18 Halted 0 ms 0 KB -