oj.uz

Submission #903248

# Submission time Handle Problem Language Result Execution time Memory
903248 2024-01-11T06:33:06 Z simona1230 Inside information (BOI21_servers) C++17
5 / 100
 1995 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+1>=y)cout<<"yes"<<endl;
                else cout<<"no"<<endl;
            }
            else
            {
                ver=find_de(ver-1);
                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 148 ms 3668 KB Output is correct
2 Correct 178 ms 65876 KB Output is correct
3 Correct 212 ms 66020 KB Output is correct
4 Correct 202 ms 66308 KB Output is correct
5 Correct 181 ms 65880 KB Output is correct
6 Correct 189 ms 66384 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3668 KB Output is correct
2 Correct 178 ms 65876 KB Output is correct
3 Correct 212 ms 66020 KB Output is correct
4 Correct 202 ms 66308 KB Output is correct
5 Correct 181 ms 65880 KB Output is correct
6 Correct 189 ms 66384 KB Output is correct
7 Correct 143 ms 3716 KB Output is correct
8 Correct 1810 ms 66180 KB Output is correct
9 Correct 655 ms 65788 KB Output is correct
10 Correct 1995 ms 65916 KB Output is correct
11 Correct 1804 ms 65488 KB Output is correct
12 Correct 362 ms 65840 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 3700 KB Output is correct
2 Runtime error 379 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 145 ms 3700 KB Output is correct
2 Runtime error 379 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 159 ms 2908 KB Output is correct
2 Runtime error 284 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 159 ms 2908 KB Output is correct
2 Runtime error 284 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 156 ms 2640 KB Output is correct
2 Runtime error 330 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 156 ms 2640 KB Output is correct
2 Runtime error 330 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 150 ms 3048 KB Output is correct
2 Runtime error 327 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 150 ms 3048 KB Output is correct
2 Runtime error 327 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 143 ms 2636 KB Output is correct
2 Correct 187 ms 64680 KB Output is correct
3 Correct 200 ms 64700 KB Output is correct
4 Correct 215 ms 64592 KB Output is correct
5 Correct 229 ms 64612 KB Output is correct
6 Correct 179 ms 64664 KB Output is correct
7 Correct 155 ms 2732 KB Output is correct
8 Runtime error 272 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 143 ms 2636 KB Output is correct
2 Correct 187 ms 64680 KB Output is correct
3 Correct 200 ms 64700 KB Output is correct
4 Correct 215 ms 64592 KB Output is correct
5 Correct 229 ms 64612 KB Output is correct
6 Correct 179 ms 64664 KB Output is correct
7 Correct 155 ms 2732 KB Output is correct
8 Runtime error 272 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -