oj.uz

Submission #772962

# Submission time Handle Problem Language Result Execution time Memory
772962 2023-07-04T13:31:20 Z ZHIRDILBILDIZ Inside information (BOI21_servers) C++14
5 / 100
 2457 ms 379260 KB 
#include<bits/stdc++.h>
using namespace std ;
struct query
{
    char type ;
    int a, b ;
};
bool flag1 = 1 ;
int n, k ;
vector<query> v ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> k ;
    for(int i = 1 ; i < n + k ; i++)
    {
        query q ;
        cin >> q.type >> q.a ;
        if(q.type != 'C')cin >> q.b ;
        if(q.type == 'S' && q.a != 1 && q.b != 1)flag1 = 0 ;
        v.push_back(q) ;
    }
    if(n <= 4000)
    {
        set<int> s[n + 1] ;
        int kol[n + 1] = {} ;
        for(int i = 1 ; i <= n ; i++)
        {
            s[i].insert(i) ;
            kol[i] = 1 ;
        }
        for(query q : v)
        {
            if(q.type == 'S')
            {
                set<int> all ;
                for(int i : s[q.a])
                    all.insert(i) ;
                for(int i : s[q.b])
                    all.insert(i) ;
                for(int i : all)
                    if(!s[q.a].count(i) || !s[q.b].count(i))kol[i]++ ;
                s[q.a] = all ;
                s[q.b] = all ;
            }
            if(q.type == 'Q')
            {
                if(s[q.a].count(q.b))cout << "yes\n" ;
                else cout << "no\n" ;
            }
            if(q.type == 'C')
                cout << kol[q.a] << '\n' ;
        }
        return 0 ;
    }
    if(flag1)
    {
        int now = 1, ind[n + 1] = {} ;
        for(query q : v)
        {
            if(q.type == 'S')
            {
                if(!ind[q.a])
                    ind[q.a] = now ;
                if(!ind[q.b])
                    ind[q.b] = now ;
                now++ ;
            }
            if(q.type == 'Q')
            {
                if(ind[q.b] <= ind[q.a])cout << "yes\n" ;
                else cout << "no\n" ;
            }
            if(q.type == 'C')
            {
                int num = ind[q.a] ;
                if(!ind[q.a])num = now ;
                cout << now - num + 1 << '\n' ;
            }
        }
    }
    return 0 ;
}
//6 18
//S 1 2
//C 1
//C 2
//C 3
//S 1 3
//C 1
//C 2
//S 1 4
//C 1
//C 2
//Q 5 1
//S 1 5
//C 1
//C 2
//S 1 6
//Q 5 1
//Q 1 5
//C 1
//C 2
//C 3
//C 4
//C 5
//C 6

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2692 KB Output is correct
2 Correct 34 ms 4132 KB Output is correct
3 Correct 190 ms 49644 KB Output is correct
4 Correct 25 ms 3792 KB Output is correct
5 Correct 24 ms 3652 KB Output is correct
6 Correct 2308 ms 378964 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2692 KB Output is correct
2 Correct 34 ms 4132 KB Output is correct
3 Correct 190 ms 49644 KB Output is correct
4 Correct 25 ms 3792 KB Output is correct
5 Correct 24 ms 3652 KB Output is correct
6 Correct 2308 ms 378964 KB Output is correct
7 Correct 16 ms 2952 KB Output is correct
8 Correct 25 ms 4340 KB Output is correct
9 Correct 280 ms 62140 KB Output is correct
10 Correct 26 ms 3984 KB Output is correct
11 Correct 22 ms 3868 KB Output is correct
12 Correct 2346 ms 379260 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2884 KB Output is correct
2 Incorrect 38 ms 5284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2884 KB Output is correct
2 Incorrect 38 ms 5284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2744 KB Output is correct
2 Incorrect 38 ms 4340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2744 KB Output is correct
2 Incorrect 38 ms 4340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2752 KB Output is correct
2 Incorrect 35 ms 4416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2752 KB Output is correct
2 Incorrect 35 ms 4416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2820 KB Output is correct
2 Incorrect 37 ms 4376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2820 KB Output is correct
2 Incorrect 37 ms 4376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2760 KB Output is correct
2 Correct 27 ms 4256 KB Output is correct
3 Correct 204 ms 49776 KB Output is correct
4 Correct 29 ms 3852 KB Output is correct
5 Correct 24 ms 3712 KB Output is correct
6 Correct 2457 ms 379208 KB Output is correct
7 Correct 20 ms 3008 KB Output is correct
8 Incorrect 41 ms 5608 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2760 KB Output is correct
2 Correct 27 ms 4256 KB Output is correct
3 Correct 204 ms 49776 KB Output is correct
4 Correct 29 ms 3852 KB Output is correct
5 Correct 24 ms 3712 KB Output is correct
6 Correct 2457 ms 379208 KB Output is correct
7 Correct 20 ms 3008 KB Output is correct
8 Incorrect 41 ms 5608 KB Output isn't correct
9 Halted 0 ms 0 KB -