oj.uz

Submission #904068

# Submission time Handle Problem Language Result Execution time Memory
904068 2024-01-11T19:30:29 Z simona1230 Inside information (BOI21_servers) C++17
30 / 100
 1858 ms 67644 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]++;
            }
        }
        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 137 ms 5728 KB Output is correct
2 Correct 176 ms 67376 KB Output is correct
3 Correct 184 ms 67264 KB Output is correct
4 Correct 188 ms 67488 KB Output is correct
5 Correct 206 ms 67644 KB Output is correct
6 Correct 212 ms 67296 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 5728 KB Output is correct
2 Correct 176 ms 67376 KB Output is correct
3 Correct 184 ms 67264 KB Output is correct
4 Correct 188 ms 67488 KB Output is correct
5 Correct 206 ms 67644 KB Output is correct
6 Correct 212 ms 67296 KB Output is correct
7 Correct 141 ms 5724 KB Output is correct
8 Correct 1848 ms 67088 KB Output is correct
9 Correct 574 ms 67132 KB Output is correct
10 Correct 1858 ms 67092 KB Output is correct
11 Correct 1752 ms 67352 KB Output is correct
12 Correct 478 ms 67152 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 140 ms 5736 KB Output is correct
2 Correct 160 ms 7800 KB Output is correct
3 Correct 185 ms 7764 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 140 ms 5736 KB Output is correct
2 Correct 160 ms 7800 KB Output is correct
3 Correct 185 ms 7764 KB Output is correct
4 Correct 153 ms 6016 KB Output is correct
5 Correct 158 ms 7504 KB Output is correct
6 Correct 157 ms 6740 KB Output is correct
7 Correct 160 ms 6844 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 5720 KB Output is correct
2 Correct 180 ms 10252 KB Output is correct
3 Correct 171 ms 10332 KB Output is correct
4 Correct 163 ms 10208 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 5720 KB Output is correct
2 Correct 180 ms 10252 KB Output is correct
3 Correct 171 ms 10332 KB Output is correct
4 Correct 163 ms 10208 KB Output is correct
5 Correct 164 ms 5712 KB Output is correct
6 Correct 167 ms 9812 KB Output is correct
7 Correct 161 ms 10008 KB Output is correct
8 Correct 158 ms 9404 KB Output is correct
9 Correct 167 ms 9544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5788 KB Output is correct
2 Correct 169 ms 16448 KB Output is correct
3 Correct 172 ms 16468 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5788 KB Output is correct
2 Correct 169 ms 16448 KB Output is correct
3 Correct 172 ms 16468 KB Output is correct
4 Correct 151 ms 6024 KB Output is correct
5 Incorrect 189 ms 16208 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 151 ms 5764 KB Output is correct
2 Correct 175 ms 10336 KB Output is correct
3 Correct 166 ms 10320 KB Output is correct
4 Correct 190 ms 10216 KB Output is correct
5 Correct 137 ms 5716 KB Output is correct
6 Correct 180 ms 16468 KB Output is correct
7 Correct 179 ms 16460 KB Output is correct
8 Incorrect 177 ms 16532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 151 ms 5764 KB Output is correct
2 Correct 175 ms 10336 KB Output is correct
3 Correct 166 ms 10320 KB Output is correct
4 Correct 190 ms 10216 KB Output is correct
5 Correct 137 ms 5716 KB Output is correct
6 Correct 180 ms 16468 KB Output is correct
7 Correct 179 ms 16460 KB Output is correct
8 Incorrect 177 ms 16532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5744 KB Output is correct
2 Correct 177 ms 67408 KB Output is correct
3 Correct 182 ms 67452 KB Output is correct
4 Correct 170 ms 67412 KB Output is correct
5 Correct 184 ms 67196 KB Output is correct
6 Correct 184 ms 67456 KB Output is correct
7 Correct 155 ms 5712 KB Output is correct
8 Correct 157 ms 7688 KB Output is correct
9 Correct 158 ms 7760 KB Output is correct
10 Correct 160 ms 5552 KB Output is correct
11 Correct 168 ms 10304 KB Output is correct
12 Correct 179 ms 10364 KB Output is correct
13 Correct 192 ms 10316 KB Output is correct
14 Correct 136 ms 5712 KB Output is correct
15 Correct 174 ms 16472 KB Output is correct
16 Correct 191 ms 16804 KB Output is correct
17 Incorrect 167 ms 16516 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5744 KB Output is correct
2 Correct 177 ms 67408 KB Output is correct
3 Correct 182 ms 67452 KB Output is correct
4 Correct 170 ms 67412 KB Output is correct
5 Correct 184 ms 67196 KB Output is correct
6 Correct 184 ms 67456 KB Output is correct
7 Correct 155 ms 5712 KB Output is correct
8 Correct 157 ms 7688 KB Output is correct
9 Correct 158 ms 7760 KB Output is correct
10 Correct 160 ms 5552 KB Output is correct
11 Correct 168 ms 10304 KB Output is correct
12 Correct 179 ms 10364 KB Output is correct
13 Correct 192 ms 10316 KB Output is correct
14 Correct 136 ms 5712 KB Output is correct
15 Correct 174 ms 16472 KB Output is correct
16 Correct 191 ms 16804 KB Output is correct
17 Incorrect 167 ms 16516 KB Output isn't correct
18 Halted 0 ms 0 KB -