Submission #1240845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240845		KindaGoodGames	Inside information (BOI21_servers)	C++17	0 / 100	3600 ms	114500 KiB

servers

#include<bits/stdc++.h>

using namespace std;
#define tcii tuple<char,int,int>

const int BLOCKS = 32;
const int MAXN = 120000;
const int MAXBLOCK = MAXN/BLOCKS;

#define bsS bitset<MAXBLOCK>
#define bsL bitset<MAXN>

vector<tcii> queries;
// bs obtained[MAXN];

vector<int> ans;
int n, q;

void solve(int k){
    int L = k*MAXBLOCK;
    int R = (k+1)*MAXBLOCK;
    vector<bsS> obtained(n);
    vector<bsL> available(MAXBLOCK);

    
    for(int i = min(L,n); i < min(R,n); i++){
        obtained[i][i-L] = true; 
        available[i-L][i] = true;
    }


    for(int t = 0; t < n+q-1; t++){
        char m;
        m = get<0>(queries[t]);

        if(m == 'S'){
            int a,b;
            a = get<1>(queries[t]);
            b = get<2>(queries[t]);
             
            obtained[a] |= obtained[b];
            obtained[b] |= obtained[a]; 

            for(int i = 0; i < MAXBLOCK; i++){
                available[i][a] = obtained[a][i];
                available[i][b] = obtained[b][i];
            }
        }
        if(m == 'Q'){
            int a,d;
            a = get<1>(queries[t]);
            d = get<2>(queries[t]);

            if(d < L || d >= R) continue;
            a = get<1>(queries[t]);
            d = get<2>(queries[t]);
            
            ans[t] = obtained[a][d-L];
        }
        if(m == 'C'){
            int d; 
            d = get<1>(queries[t]);
             
            if(d < L || d >= R) continue; 
            ans[t] = available[d-L].count(); 
        }
    }
}   

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    queries.resize(n+q-1); 
    ans.resize(n+q+1);
    

    for(int t = 0; t < n+q-1; t++){
        char m;
        cin >> m;

        if(m == 'S'){
            int a,b;
            cin >> a >> b;
            a--;b--;
            queries[t] = {m,a,b};
        }
        if(m == 'Q'){
            int a,d;
            cin >> a >> d;
            a--;d--;
            queries[t] = {m,a,d};
        }
        if(m == 'C'){
            int d;
            cin >> d;
            d--;
            queries[t] = {m,d,-42};
        }
    }

    for(int k = 0; k < BLOCKS; k++){
        solve(k);
    }

    for(int i = 0; i < n+q-1; i++){
        if(get<0>(queries[i]) == 'Q'){
            cout << (ans[i] ? "yes" : "no") << "\n";
        }
        if(get<0>(queries[i]) == 'C'){
            cout << ans[i] << "\n";
        }
    }
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18