oj.uz

Submission #903243

# Submission time Handle Problem Language Result Execution time Memory
903243 2024-01-11T06:30:56 Z simona1230 Inside information (BOI21_servers) C++17
5 / 100
 1787 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

int n,k;
int in[4001][4001];

void slow()
{
    for(int i=1;i<=n;i++)
        in[i][i]=1;
    for(int i=1;i<=n+k-1;i++)
    {
        char c;
        cin>>c;
        int x,y;
        if(c=='S')
        {
            cin>>x>>y;
            for(int j=1;j<=n;j++)
            {
                in[x][j]=in[y][j]=max(in[x][j],in[y][j]);
            }
        }
        if(c=='C')
        {
            cin>>x;
            int cnt=0;
            for(int j=1;j<=n;j++)
                cnt+=in[j][x];
            cout<<cnt<<endl;
        }
        if(c=='Q')
        {
            cin>>x>>y;
            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++)
    {
        char c;
        cin>>c;

        if(c=='S')
        {
            int x,y;
            cin>>x>>y;

            t[max(x,y)]=sec++;
        }

        if(c=='Q')
        {
            int x,y;
            cin>>x>>y;

            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')
        {
            int x;
            cin>>x;

            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(ver);
}
int find_de(int ver)
{
    if(ver==de[ver])return ver;
    return de[ver]=find_de(ver);
}

void subt3()
{
    int sec=1;
    for(int i=1;i<=n+k-1;i++)
    {
        int x,y;
        char c;
        cin>>c>>x;
        if(c=='S')
        {
            cin>>y;
            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')
        {
            cin>>y;
            int ver=x;
            if(y>x)
            {
                ver=find_inc(ver);
                if(ver>=y)cout<<"yes"<<endl;
                else cout<<"no"<<endl;
            }
            else
            {
                ver=find_de(ver);
                if(ver<=y)cout<<"yes"<<endl;
                else cout<<"no"<<endl;
            }
        }
    }
}

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

	cin>>n>>k;
	if(n<=4000)slow();
    else subt3();

	return 0;
}

Compilation message

servers.cpp: In function 'void subt2()':
servers.cpp:66:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |             if(t[y]&&t[y]<=t[x]||x==1&&t[y]||y==1&&t[x]||x==y)cout<<"yes"<<endl;
      |                ~~~~^~~~~~~~~~~~
servers.cpp:66:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |             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 166 ms 3676 KB Output is correct
2 Correct 183 ms 66060 KB Output is correct
3 Correct 192 ms 66072 KB Output is correct
4 Correct 186 ms 65920 KB Output is correct
5 Correct 202 ms 66072 KB Output is correct
6 Correct 194 ms 66280 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 166 ms 3676 KB Output is correct
2 Correct 183 ms 66060 KB Output is correct
3 Correct 192 ms 66072 KB Output is correct
4 Correct 186 ms 65920 KB Output is correct
5 Correct 202 ms 66072 KB Output is correct
6 Correct 194 ms 66280 KB Output is correct
7 Correct 176 ms 3720 KB Output is correct
8 Correct 1725 ms 65724 KB Output is correct
9 Correct 568 ms 66036 KB Output is correct
10 Correct 1704 ms 65948 KB Output is correct
11 Correct 1787 ms 65752 KB Output is correct
12 Correct 401 ms 65704 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 181 ms 3732 KB Output is correct
2 Runtime error 371 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 181 ms 3732 KB Output is correct
2 Runtime error 371 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 3720 KB Output is correct
2 Runtime error 308 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 3720 KB Output is correct
2 Runtime error 308 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3720 KB Output is correct
2 Runtime error 310 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3720 KB Output is correct
2 Runtime error 310 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3972 KB Output is correct
2 Runtime error 285 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3972 KB Output is correct
2 Runtime error 285 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 158 ms 3580 KB Output is correct
2 Correct 206 ms 65872 KB Output is correct
3 Correct 217 ms 66136 KB Output is correct
4 Correct 194 ms 66032 KB Output is correct
5 Correct 183 ms 66076 KB Output is correct
6 Correct 224 ms 66088 KB Output is correct
7 Correct 162 ms 3748 KB Output is correct
8 Runtime error 300 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 158 ms 3580 KB Output is correct
2 Correct 206 ms 65872 KB Output is correct
3 Correct 217 ms 66136 KB Output is correct
4 Correct 194 ms 66032 KB Output is correct
5 Correct 183 ms 66076 KB Output is correct
6 Correct 224 ms 66088 KB Output is correct
7 Correct 162 ms 3748 KB Output is correct
8 Runtime error 300 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -