Блог пользователя rahul_1234

Автор rahul_1234, история, 7 лет назад, По-английски

You have a set of N objects. Each of these objects have certain properties associated with them. A property is represented by a (key, value) pair. For example, assume you have the following two objects.

Tower: { (height, 100), (weight, 50), (xposition, 25), (yposition, 36) }

Tree: { (area, 100), (noofleaves, 500), (height, 25), (yposition, 36) }

Each object you have, will have at most 4 properties. An object will have at least 1 property. Note, from the two objects above, that it is not necessary for key in the properties to be same for all the objects. Also, it is not necessary for the key to be different. Now, given N such objects, you wish to answer M queries. Each query is represented by a set of properties (again, at most 4 properties, and at least 1 property). The answer for the query is the number of objects in the set, that have all the given properties. Two properties are considered equal iff both the key and the value match. For example, if you have the above two objects, then the answer for the following queries is

Query: { (height, 100), (yposition, 36) }

Answer: 1 // matches Tower, but not Tree

Query: { (yposition, 36) }

Answer: 2 // matches both Tower and Tree

Query: { (height, 100), (noofleaves, 500) }

Answer: 0 // neither Tower, not Tree satisfy both properties

Input:

The first line of input contains N and M. This is followed by the description of the N objects. The description of the i-th object will start by a number k, which is the number of properties associated with the object. The next k lines contain two space separated strings – the property key and the property value. Note that the property value is not necessarily an integer (although this is so for the example above). This is followed by the description of M queries. The format of a query will be exactly same to that of the objects. Check the Sample Input for clarification. One test file will contain only one test case. A single test case may contain several queries.

Output:

Print M lines. Each line must be the answer of the respective query.

Constraints:

1 <= N <= 10000

1 <= M <= 100000

1 <= k <= 4

Sample Input 2 3

4

height 100a

weight 50b

xposition 25a

yposition 36b

4

area 100a

noofleaves 500

height 25

yposition 36b

3

weight 80

xposition 25a

yposition 36b

1

yposition 36b

2

xposition 25a

yposition 36b

Sample Output:

0

2

1

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Identify each existent (key,value) pair with a number (at most 40000 different numbers). For each object, assign a unique id to it and consider all subobjects (all subsets of its properties), represented as sorted vectors. Use a map<subobject, containing_objects> (vector to vector) with at most 2^4 * 10000 keys to quickly relate subobjects to all containing objects. Now an answer to a query for suboject S is just map[S].

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you mean map[S].size()?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If you just want the size, yeah, but you have all the objects there as well.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I am just pointing out the error in this sentences. Now an answer to a query for suboject S is just map[S].