Submission #1240657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240657		KindaGoodGames	Inside information (BOI21_servers)	C++17	2 / 100	62 ms	19596 KiB

servers

#include<bits/stdc++.h>

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

const int MAXN = 4000;
const int MAXBLOCK = 4000/4;
#define bs bitset<MAXBLOCK>

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<bs> obtained(n);

    
    for(int i = min(L,n); i < min(R,n); i++){
        obtained[i][i-L] = 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]; 
        }
        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];
        }
    }
}   

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};
        }
    }

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

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

• Subtask 1-1: 2 / 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