Untitled
user_9860231815
plain_text
a year ago
4.0 kB
1
Indexable
Never
#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std ; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); #define DISPLAY(V) for(auto it : V) { cout<<it<<" " ;} cout<<endl; #define DISPLAY2(V) for(auto it : V) { for (auto val : it) { cout<<val<<" ";} cout<<endl;} #define mod 1000000007ll #define sz(x) (ll)x.size() #define all(x) x.begin(),x.end() #define see(x) cerr<<#x<<" = "; _print(x);cerr<<endl; typedef long long ll ; typedef long double ld; typedef vector <ll> vll; typedef vector <char> vch; typedef vector <string> vs; void _print(ll t) {cerr << t;} void _print(string t) {cerr << t;} void _print(char t) {cerr << t;} void _print(double t) {cerr << t;} template <class T, class V> void _print(pair <T, V> p){cerr<< "{";_print(p.first);cerr<<",";_print(p.second);cerr<<"}";} template <class T> void _print(vector <T> v){cerr<<"[ ";for(T i: v){_print(i);cerr<<" ";}cerr << "]";} template <class T> void _print(set <T> v){cerr<<"[ ";for(T i: v){_print(i);cerr<<" ";}cerr << "]";} template <class T> void _print(multiset <T> v){cerr<<"[ ";for(T i: v){_print(i);cerr<<" ";}cerr << "]";} template <class T, class V> void _print(map <T, V> v){cerr<<"[ ";for(auto i: v){_print(i);cerr<<" ";}cerr << "]";} ll expo(ll x, ll y) { ll res = 1; while (y) {if (y % 2) res = (res * x % mod) % mod; x = (x * x) % mod; y /= 2; } return res;} ll inv(ll x) {return expo(x, mod - 2);} ll add(ll a, ll b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;} ll mul(ll a, ll b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;} ll sub(ll a, ll b) {a = a % mod; b = b % mod; return (((a - b) % mod) + mod) % mod;} ll m_div(ll a, ll b) {a = a % mod; b = b % mod; return (mul(a, inv(b)) + mod) % mod;} inline ll myceil(ll a , ll b){ if(a%b==0) return a/b ; else return a/b+1 ; } inline ll lcm(ll a , ll b) {return (a*b)/__gcd(a,b) ;} bool isPerSquare(ll a) {if(a<0) return false; ll sr = sqrt(a); return (sr*sr == a);} int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; bool dfs(vector<vll> &g , vll & lock , ll node) { if(lock[node]!=0) return 0 ; for(auto & i : g[node]) { if(dfs(g,lock,node)==0) return 0; } return 1; } void solve() { ll n , m,q ; cin>>n>>m>>q; vector<string> v(n+1); for(ll i = 1 ; i<=n; ++i) cin >> v[i]; map<string, ll> id; for(ll i = 1 ; i<=n; ++i) id[v[i]] = i; queue<ll> vq; vq.push(1); vector<vll> g(n + 1); vll par(n + 1); ll ind = 2; while(!vq.empty()) { ll node = vq.front(); vq.pop(); ll cnt = 0; while(cnt<m) { if(ind==n+1) { break; } vq.push(ind); par[ind] = node ; g[node].push_back(ind); ind++; cnt++ ; } } vll locked(n + 1, 0); while(q--) { ll t, user; cin>>t ; string c ; cin>>c>>user ; if(t==1) { ll ok = 1 ; ll p = id[c]; while(p!=0) { if(locked[p]!=0) { ok = 0 ; break ; } p = par[p]; } p = id[c]; if(dfs(g,locked,p)==0) ok = 0; if(ok==0) { cout << "false\n"; } else { cout << "true\n"; locked[p] = user; } } } } int main() { fast ; ll t = 1; // cin>>t; for(ll i = 1 ;i<=t; ++i) { //cout << "Case #"<<i<<": "; solve(); } return 0 ; }