oj.uz

Submission #772946

# Submission time Handle Problem Language Result Execution time Memory
772946 2023-07-04T13:24:49 Z ZHIRDILBILDIZ Inside information (BOI21_servers) C++14
5 / 100
 2241 ms 378804 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] + 1 << '\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
//C 2
//C 3
//C 4
//C 5
//C 6

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2504 KB Output is correct
2 Correct 34 ms 3904 KB Output is correct
3 Correct 190 ms 49388 KB Output is correct
4 Correct 25 ms 3520 KB Output is correct
5 Correct 23 ms 3368 KB Output is correct
6 Correct 2232 ms 378640 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2504 KB Output is correct
2 Correct 34 ms 3904 KB Output is correct
3 Correct 190 ms 49388 KB Output is correct
4 Correct 25 ms 3520 KB Output is correct
5 Correct 23 ms 3368 KB Output is correct
6 Correct 2232 ms 378640 KB Output is correct
7 Correct 16 ms 2496 KB Output is correct
8 Correct 26 ms 4016 KB Output is correct
9 Correct 234 ms 61732 KB Output is correct
10 Correct 23 ms 3620 KB Output is correct
11 Correct 22 ms 3384 KB Output is correct
12 Correct 2241 ms 378804 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2504 KB Output is correct
2 Incorrect 37 ms 4664 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 2504 KB Output is correct
2 Incorrect 37 ms 4664 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 2392 KB Output is correct
2 Incorrect 38 ms 3916 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 2392 KB Output is correct
2 Incorrect 38 ms 3916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2376 KB Output is correct
2 Incorrect 37 ms 3812 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 2404 KB Output is correct
2 Incorrect 44 ms 3900 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 2404 KB Output is correct
2 Incorrect 44 ms 3900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2464 KB Output is correct
2 Correct 27 ms 3892 KB Output is correct
3 Correct 212 ms 49368 KB Output is correct
4 Correct 28 ms 3584 KB Output is correct
5 Correct 24 ms 3384 KB Output is correct
6 Correct 2131 ms 378756 KB Output is correct
7 Correct 16 ms 2408 KB Output is correct
8 Incorrect 39 ms 4644 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2464 KB Output is correct
2 Correct 27 ms 3892 KB Output is correct
3 Correct 212 ms 49368 KB Output is correct
4 Correct 28 ms 3584 KB Output is correct
5 Correct 24 ms 3384 KB Output is correct
6 Correct 2131 ms 378756 KB Output is correct
7 Correct 16 ms 2408 KB Output is correct
8 Incorrect 39 ms 4644 KB Output isn't correct
9 Halted 0 ms 0 KB -