oj.uz

Submission #904037

# Submission time Handle Problem Language Result Execution time Memory
904037 2024-01-11T18:15:04 Z simona1230 Inside information (BOI21_servers) C++17
10 / 100
 1648 ms 68240 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;
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;
    }
}
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];
        cout<<c<<" "<<x<<" "<<y<<endl;
        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 main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	read();
	if(n<=4000)slow();
    else if(sbt2)subt2();
    else subt3();

	return 0;
}

Compilation message

servers.cpp: In function 'void subt2()':
servers.cpp:73:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |             if(t[y]&&t[y]<=t[x]||x==1&&t[y]||y==1&&t[x]||x==y)cout<<"yes"<<endl;
      |                ~~~~^~~~~~~~~~~~
servers.cpp:73:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |             if(t[y]&&t[y]<=t[x]||x==1&&t[y]||y==1&&t[x]||x==y)cout<<"yes"<<endl;
      |                                              ~~~~^~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 148 ms 5740 KB Output is correct
2 Correct 174 ms 68188 KB Output is correct
3 Correct 182 ms 67980 KB Output is correct
4 Correct 176 ms 68032 KB Output is correct
5 Correct 205 ms 68176 KB Output is correct
6 Correct 175 ms 68136 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 148 ms 5740 KB Output is correct
2 Correct 174 ms 68188 KB Output is correct
3 Correct 182 ms 67980 KB Output is correct
4 Correct 176 ms 68032 KB Output is correct
5 Correct 205 ms 68176 KB Output is correct
6 Correct 175 ms 68136 KB Output is correct
7 Correct 139 ms 5756 KB Output is correct
8 Correct 1636 ms 67936 KB Output is correct
9 Correct 418 ms 67896 KB Output is correct
10 Correct 1648 ms 68064 KB Output is correct
11 Correct 1615 ms 68180 KB Output is correct
12 Correct 360 ms 67920 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5712 KB Output is correct
2 Correct 181 ms 8064 KB Output is correct
3 Correct 161 ms 7712 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5712 KB Output is correct
2 Correct 181 ms 8064 KB Output is correct
3 Correct 161 ms 7712 KB Output is correct
4 Correct 143 ms 5732 KB Output is correct
5 Correct 180 ms 7464 KB Output is correct
6 Correct 152 ms 6892 KB Output is correct
7 Correct 159 ms 7036 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5756 KB Output is correct
2 Incorrect 482 ms 11868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5756 KB Output is correct
2 Incorrect 482 ms 11868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 5712 KB Output is correct
2 Incorrect 457 ms 11860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 5712 KB Output is correct
2 Incorrect 457 ms 11860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5628 KB Output is correct
2 Incorrect 492 ms 11864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5628 KB Output is correct
2 Incorrect 492 ms 11864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5784 KB Output is correct
2 Correct 173 ms 68016 KB Output is correct
3 Correct 176 ms 68160 KB Output is correct
4 Correct 179 ms 67992 KB Output is correct
5 Correct 177 ms 67972 KB Output is correct
6 Correct 192 ms 68240 KB Output is correct
7 Correct 138 ms 5736 KB Output is correct
8 Correct 161 ms 7760 KB Output is correct
9 Correct 164 ms 7788 KB Output is correct
10 Correct 140 ms 5712 KB Output is correct
11 Incorrect 475 ms 11848 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5784 KB Output is correct
2 Correct 173 ms 68016 KB Output is correct
3 Correct 176 ms 68160 KB Output is correct
4 Correct 179 ms 67992 KB Output is correct
5 Correct 177 ms 67972 KB Output is correct
6 Correct 192 ms 68240 KB Output is correct
7 Correct 138 ms 5736 KB Output is correct
8 Correct 161 ms 7760 KB Output is correct
9 Correct 164 ms 7788 KB Output is correct
10 Correct 140 ms 5712 KB Output is correct
11 Incorrect 475 ms 11848 KB Output isn't correct
12 Halted 0 ms 0 KB -