Code length limit 16 KB
Time limit 400 ms
Memory limit 64 MB

Title Description

Insert a series of given numbers into a small top heap H [], which is initially empty. Then judge whether a series of related propositions are true. Propositions are divided into the following categories:

x is the root: x Is the root node;
x and y are siblings: x and y Is a brother node;
x is the parent of y: x yes y Parent node of;
x is a child of y: x yes y A child node of.

Input format

The first line of each test group contains two positive integers N (≤ 1000) and M (≤ 20), which are the number of inserted elements and the number of propositions to be judged. The next line gives N integers in the interval [− 1000010000] to be inserted into a small top heap that is initially empty. Then M lines, each line gives a proposition. The topic ensures that the node key values in the proposition exist.

Output format

For each proposition input, if it is true, output T in one line, otherwise output F.

sample input

5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

sample output

F
T
F
T

Personal thinking

1. Use a vector < int > to store the node key value, and then use it to create a small top heap
2. Building a small top pile stepped on a pit. It was originally intended to use makeheap to build a small top pile at one time, but there were two test points that couldn't pass. The reason is that when using makeheap to create a small top heap, the leaf nodes will automatically sort the size, rather than simply inserting them one by one according to the order of the two-dimensional array (this method of manually creating a small top heap is also recorded in the commented part of the code). Therefore, you can continuously make heap during dynamic input insertion or use the pushleap () method. So we can pass.
3. All propositions are stored in a two-dimensional dynamic array. Here, istringstream type is used to obtain the string, and then while is used to process it. By dividing the string with spaces, each word of each proposition can be stored separately.
4. Finally, judge each proposition according to the characteristics of various propositions
5. In addition, there is a small pit, that is, when judging the number subscript, you need to convert the string to integer first. Because there is a negative number in the range of node key value, you need to judge the symbol of the first character.
6. Of course, the method of dynamic two-dimensional array can also be avoided, because it only needs to judge the second (used to judge whether the third is to obtain a string or an integer) and the fourth word of each command to distinguish different commands, and then directly obtain the integer value at the position where the number is reached, so as to avoid some pits that may be encountered by turning the number.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<ll> v;
ll getsum(string s)
{
    ll rtn=0;
    int flag=1;
    if(s[0]=='-')
    {
        flag=-1;
    }
    else
    {
        flag=1;
        rtn=s[0]-'0';
    }
    for(ll i=1;i<s.length();i++)
    {
        rtn=rtn*10+(s[i]-'0');
    }
    //cout<<rtn<<endl;
    rtn*=flag;
    for(ll i=0;i<v.size();i++)
    {
        if(rtn==v[i])
            return i;
    }
    return -1;
}
int main()
{
    ll n,m;
    cin>>n>>m;
    /*for (int i = 0; i < n;i++){//Build small top pile
        int a;
        cin>>a;
        v.push_back(a);
		int k=i;
		while(k>0&&v[k]<v[(k-1)/2]){
			swap(v[k],v[(k-1)/2]);
			k=(k-1)/2;
		}
	}*/
    while(n--)
    {
        ll x;
        cin>>x;
        v.push_back(x);
        push_heap(v.begin(),v.end(),greater<ll>()); 
    }
    
    //for(int i=0;i<v.size();i++)
       //cout<<v[i]<<" ";
    //cout<<endl;
    vector<vector<string>> vv;
    getchar();
    while(m--)
    {
        string str;
        getline(cin,str);
        vector<string> vt;
        
        istringstream s(str);
        string out;
        while(s>>out)
        {
            vt.push_back(out);
        }
        vv.push_back(vt);
        vt.clear();
    }
    /*for(int i=0;i<vv.size();i++)
    {
        for(int j=0;j<vv[i].size();j++)
        {
            cout<<vv[i][j]<<" ";
        }
        cout<<endl;
    }*/
    for(ll i=0;i<vv.size();i++)
    {
        if(vv[i][1]=="and")
        {
            ll x=getsum(vv[i][0]);
            ll y=getsum(vv[i][2]);
            if(x==-1||y==-1)
            {
                cout<<"F"<<endl;
                continue;
            }
            if(((x-1)/2)==((y-1)/2))
                cout<<"T"<<endl;
            else
                cout<<"F"<<endl;
        }
        else if(vv[i][3]=="child")
        {
            ll x=getsum(vv[i][0]);
            ll y=getsum(vv[i][5]);
            if(x==-1||y==-1)
            {
                cout<<"F"<<endl;
                continue;
            }
            if(y==((x-1)/2))
                cout<<"T"<<endl;
            else
                cout<<"F"<<endl;
        }
       else if(vv[i][3]=="root") /**/
        {
            if(getsum(vv[i][0])==-1||getsum(vv[i][0])==-1)
            {
                cout<<"F"<<endl;
                continue;
            }
            if(getsum(vv[i][0])==0)
                cout<<"T"<<endl;
            else
                cout<<"F"<<endl;
        }
        else
        {
            ll x=getsum(vv[i][0]);
            ll y=getsum(vv[i][5]);
            if(x==-1||y==-1)
            {
                cout<<"F"<<endl;
                continue;
            }
            if(x==(y-1)/2)
                cout<<"T"<<endl;
            else
                cout<<"F"<<endl;
        }
    }
}