Submission #1240653

#TimeUsernameProblemLanguageResultExecution timeMemory
1240653KindaGoodGamesInside information (BOI21_servers)C++20
0 / 100
9 ms2368 KiB
#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 = L; i < R; 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"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...