oj.uz

Submission #772915

# Submission time Handle Problem Language Result Execution time Memory
772915 2023-07-04T12:52:18 Z ZHIRDILBILDIZ Inside information (BOI21_servers) C++14
5 / 100
 2254 ms 379940 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')
                cout << now - ind[q.a] << '\n' ;
        }
    }
    return 0 ;
}
//6 9
//S 1 2
//S 1 3
//S 1 4
//Q 5 1
//S 1 5
//S 1 6
//Q 5 1
//Q 1 5
//C 1

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2988 KB Output is correct
2 Correct 26 ms 5020 KB Output is correct
3 Correct 196 ms 50460 KB Output is correct
4 Correct 33 ms 4696 KB Output is correct
5 Correct 24 ms 4536 KB Output is correct
6 Correct 2206 ms 379904 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2988 KB Output is correct
2 Correct 26 ms 5020 KB Output is correct
3 Correct 196 ms 50460 KB Output is correct
4 Correct 33 ms 4696 KB Output is correct
5 Correct 24 ms 4536 KB Output is correct
6 Correct 2206 ms 379904 KB Output is correct
7 Correct 17 ms 3000 KB Output is correct
8 Correct 25 ms 4656 KB Output is correct
9 Correct 236 ms 62356 KB Output is correct
10 Correct 27 ms 4308 KB Output is correct
11 Correct 21 ms 4156 KB Output is correct
12 Correct 2226 ms 379740 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3096 KB Output is correct
2 Incorrect 46 ms 5548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3096 KB Output is correct
2 Incorrect 46 ms 5548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3064 KB Output is correct
2 Incorrect 36 ms 4696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3064 KB Output is correct
2 Incorrect 36 ms 4696 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 3112 KB Output is correct
2 Incorrect 38 ms 4672 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 3112 KB Output is correct
2 Incorrect 38 ms 4672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3016 KB Output is correct
2 Incorrect 36 ms 4788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3016 KB Output is correct
2 Incorrect 36 ms 4788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3068 KB Output is correct
2 Correct 29 ms 5060 KB Output is correct
3 Correct 227 ms 50568 KB Output is correct
4 Correct 31 ms 4684 KB Output is correct
5 Correct 23 ms 4536 KB Output is correct
6 Correct 2254 ms 379940 KB Output is correct
7 Correct 17 ms 3144 KB Output is correct
8 Incorrect 38 ms 5532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3068 KB Output is correct
2 Correct 29 ms 5060 KB Output is correct
3 Correct 227 ms 50568 KB Output is correct
4 Correct 31 ms 4684 KB Output is correct
5 Correct 23 ms 4536 KB Output is correct
6 Correct 2254 ms 379940 KB Output is correct
7 Correct 17 ms 3144 KB Output is correct
8 Incorrect 38 ms 5532 KB Output isn't correct
9 Halted 0 ms 0 KB -