oj.uz

Submission #729124

# Submission time Handle Problem Language Result Execution time Memory
729124 2023-04-23T14:33:50 Z Jean7 Inside information (BOI21_servers) C++14
10 / 100
 96 ms 17000 KB 
#include <bits/stdc++.h>
#define int long long
 
using namespace std ;
 
bool cnt[4002][4002] ;
int n , k , ans[4002] , in[200005] ;
 
inline void solve () {
    cin >> n >> k ;
    if ( n > 4000 ) {
        int cnt = 0 ;
        for ( int i = 1 ; i <= n + k - 1 ; i++ ) {
            char c ; int x , y ;
            cin >> c ;
            if ( c == 'S' ) {
                cnt++ ;
                cin >> x >> y ;
                if ( !in[x] ) {
                    in[x] = cnt ;
                }
                if ( !in[y] ) {
                    in[y] = cnt ;
                }
            }
            else if ( c == 'Q' ) {
                cin >> x >> y ;
                if ( !in[x] || !in[y] ) {
                    cout << "no\n" ;
                }
                else {
                    if ( x == 1 ) {
                        cout << "yes\n" ;
                    }
                    else if ( in[x] >= in[y] ) {
                        cout << "yes\n" ;
                    }
                    else {
                        cout << "no\n" ;
                    }
                }
            }
            else {
                cin >> x ;
                if ( !in[x] ) {
                    cout << 1 << "\n" ;
                }
                else {
                    cout << cnt - in[x] + 2 << "\n" ;
                }
            }
        }
        return ;
    }
    for ( int i = 1 ; i <= n ; i++ ) {
        cnt[i][i] = 1 ;
        ans[i]++ ;
    }
    for ( int i = 1 ; i <= n + k - 1 ; i++ ) {
        char c ;
        int x , y ;
        cin >> c ;
        if ( c == 'S' ) {
            cin >> x >> y ;
            for ( int i = 1 ; i <= n ; i++ ) {
                if ( cnt[x][i] || cnt[y][i] ) {
                    ans[i] += 2 - cnt[x][i] - cnt[y][i] ;
                    cnt[x][i] = cnt[y][i] = 1 ;
                }
            }
        }
        else if ( c == 'Q' ) {
            cin >> x >> y ;
            cout << ( cnt[x][y] ? "yes\n" : "no\n" ) ;
        }
        else {
            cin >> x ;
            cout << ans[x] << "\n" ;
        }
    }
}
 
signed main () {
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;
    int tc = 1 ;
    //cin >> tc ;
    while ( tc-- ) {
        solve() ;
    }
    return 0 ;
}
 
///  JJJJJJJ EEEEEEE  AAAAA  NN   NN 7777777
///     JJ   EE      AA   AA NNN  NN     77
///     JJ   EEEEEE  AAAAAAA NN N NN    77
///  JJ JJ   EE      AA   AA NN  NNN   77
///  JJJJJ   EEEEEEE AA   AA NN   NN  77

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1336 KB Output is correct
2 Correct 58 ms 16820 KB Output is correct
3 Correct 62 ms 16872 KB Output is correct
4 Correct 67 ms 16800 KB Output is correct
5 Correct 55 ms 16844 KB Output is correct
6 Correct 82 ms 17000 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1336 KB Output is correct
2 Correct 58 ms 16820 KB Output is correct
3 Correct 62 ms 16872 KB Output is correct
4 Correct 67 ms 16800 KB Output is correct
5 Correct 55 ms 16844 KB Output is correct
6 Correct 82 ms 17000 KB Output is correct
7 Correct 21 ms 1368 KB Output is correct
8 Correct 55 ms 16732 KB Output is correct
9 Correct 60 ms 16924 KB Output is correct
10 Correct 52 ms 16728 KB Output is correct
11 Correct 56 ms 16776 KB Output is correct
12 Correct 96 ms 16984 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 852 KB Output is correct
2 Correct 45 ms 1636 KB Output is correct
3 Correct 44 ms 1740 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 852 KB Output is correct
2 Correct 45 ms 1636 KB Output is correct
3 Correct 44 ms 1740 KB Output is correct
4 Correct 19 ms 872 KB Output is correct
5 Correct 52 ms 1736 KB Output is correct
6 Correct 37 ms 1972 KB Output is correct
7 Correct 41 ms 1860 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1356 KB Output is correct
2 Incorrect 53 ms 5004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1356 KB Output is correct
2 Incorrect 53 ms 5004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1376 KB Output is correct
2 Incorrect 47 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1376 KB Output is correct
2 Incorrect 47 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1328 KB Output is correct
2 Incorrect 52 ms 4928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1328 KB Output is correct
2 Incorrect 52 ms 4928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1292 KB Output is correct
2 Correct 61 ms 16856 KB Output is correct
3 Correct 59 ms 16844 KB Output is correct
4 Correct 58 ms 16856 KB Output is correct
5 Correct 58 ms 16796 KB Output is correct
6 Correct 89 ms 16844 KB Output is correct
7 Correct 21 ms 1484 KB Output is correct
8 Correct 50 ms 4504 KB Output is correct
9 Correct 48 ms 4508 KB Output is correct
10 Correct 18 ms 1692 KB Output is correct
11 Incorrect 49 ms 4936 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1292 KB Output is correct
2 Correct 61 ms 16856 KB Output is correct
3 Correct 59 ms 16844 KB Output is correct
4 Correct 58 ms 16856 KB Output is correct
5 Correct 58 ms 16796 KB Output is correct
6 Correct 89 ms 16844 KB Output is correct
7 Correct 21 ms 1484 KB Output is correct
8 Correct 50 ms 4504 KB Output is correct
9 Correct 48 ms 4508 KB Output is correct
10 Correct 18 ms 1692 KB Output is correct
11 Incorrect 49 ms 4936 KB Output isn't correct
12 Halted 0 ms 0 KB -