Untitled

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