oj.uz

Submission #904043

# Submission time Handle Problem Language Result Execution time Memory
904043 2024-01-11T18:19:38 Z simona1230 Inside information (BOI21_servers) C++17
20 / 100
 1628 ms 68092 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];
        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 136 ms 4700 KB Output is correct
2 Correct 177 ms 67764 KB Output is correct
3 Correct 192 ms 67824 KB Output is correct
4 Correct 191 ms 67692 KB Output is correct
5 Correct 172 ms 67708 KB Output is correct
6 Correct 187 ms 67868 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 136 ms 4700 KB Output is correct
2 Correct 177 ms 67764 KB Output is correct
3 Correct 192 ms 67824 KB Output is correct
4 Correct 191 ms 67692 KB Output is correct
5 Correct 172 ms 67708 KB Output is correct
6 Correct 187 ms 67868 KB Output is correct
7 Correct 177 ms 5476 KB Output is correct
8 Correct 1628 ms 67800 KB Output is correct
9 Correct 456 ms 67548 KB Output is correct
10 Correct 1588 ms 67408 KB Output is correct
11 Correct 1612 ms 67340 KB Output is correct
12 Correct 441 ms 67920 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4912 KB Output is correct
2 Correct 168 ms 6604 KB Output is correct
3 Correct 157 ms 6612 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4912 KB Output is correct
2 Correct 168 ms 6604 KB Output is correct
3 Correct 157 ms 6612 KB Output is correct
4 Correct 168 ms 5584 KB Output is correct
5 Correct 190 ms 6308 KB Output is correct
6 Correct 151 ms 6248 KB Output is correct
7 Correct 160 ms 6364 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 4748 KB Output is correct
2 Correct 176 ms 6752 KB Output is correct
3 Correct 194 ms 8308 KB Output is correct
4 Correct 161 ms 8248 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 4748 KB Output is correct
2 Correct 176 ms 6752 KB Output is correct
3 Correct 194 ms 8308 KB Output is correct
4 Correct 161 ms 8248 KB Output is correct
5 Correct 154 ms 5656 KB Output is correct
6 Correct 179 ms 8016 KB Output is correct
7 Correct 162 ms 8120 KB Output is correct
8 Correct 182 ms 7688 KB Output is correct
9 Correct 167 ms 7616 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 4840 KB Output is correct
2 Incorrect 172 ms 6848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 4840 KB Output is correct
2 Incorrect 172 ms 6848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4828 KB Output is correct
2 Correct 169 ms 6752 KB Output is correct
3 Correct 179 ms 8504 KB Output is correct
4 Correct 188 ms 8312 KB Output is correct
5 Correct 137 ms 5716 KB Output is correct
6 Incorrect 176 ms 8372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4828 KB Output is correct
2 Correct 169 ms 6752 KB Output is correct
3 Correct 179 ms 8504 KB Output is correct
4 Correct 188 ms 8312 KB Output is correct
5 Correct 137 ms 5716 KB Output is correct
6 Incorrect 176 ms 8372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 4904 KB Output is correct
2 Correct 172 ms 67704 KB Output is correct
3 Correct 180 ms 68092 KB Output is correct
4 Correct 176 ms 67668 KB Output is correct
5 Correct 195 ms 67732 KB Output is correct
6 Correct 187 ms 67976 KB Output is correct
7 Correct 146 ms 5608 KB Output is correct
8 Correct 157 ms 6724 KB Output is correct
9 Correct 163 ms 6752 KB Output is correct
10 Correct 138 ms 5456 KB Output is correct
11 Correct 164 ms 6760 KB Output is correct
12 Correct 179 ms 8328 KB Output is correct
13 Correct 161 ms 8344 KB Output is correct
14 Correct 161 ms 5772 KB Output is correct
15 Incorrect 159 ms 8516 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 4904 KB Output is correct
2 Correct 172 ms 67704 KB Output is correct
3 Correct 180 ms 68092 KB Output is correct
4 Correct 176 ms 67668 KB Output is correct
5 Correct 195 ms 67732 KB Output is correct
6 Correct 187 ms 67976 KB Output is correct
7 Correct 146 ms 5608 KB Output is correct
8 Correct 157 ms 6724 KB Output is correct
9 Correct 163 ms 6752 KB Output is correct
10 Correct 138 ms 5456 KB Output is correct
11 Correct 164 ms 6760 KB Output is correct
12 Correct 179 ms 8328 KB Output is correct
13 Correct 161 ms 8344 KB Output is correct
14 Correct 161 ms 5772 KB Output is correct
15 Incorrect 159 ms 8516 KB Output isn't correct
16 Halted 0 ms 0 KB -