Untitled

[Problem Description]

There is a magical world where strings live.

As time goes by in this world, strings whose length is in the range from 5 to 10 are born one at a time.

A string has a lifespan. After a string is born, it dies when it lives as long as its lifespan.
Let’s say that a string is born at Time 40 and its lifespan is 10. Then, it dies at Time 50.
Death Time is the time when the string dies.
 

When a string is born, it finds strings with the same “substring of at least 3 letters” as it and befriends them.
At this moment, the strings that will become friends with it should be alive and not dead.

In here, the string’s “substring” means a consecutive part within a string.
If there is a string named “embargo”, “bar” and “argo” are its substrings.
“ema” or “brgo” is NOT a substring because it is NOT a consecutive part.
“embargo” and “barber” become friends as the substring “bar” is in both of them.

The generated string and its friends and the friends’ friends all become friends.

The generated string changes the death time of the befriended string to make it the same as its own so that they die together.
The death time of string can constantly change as friends are added until its death.

 

When strings have features as above, you are required to write a program
that calculates the number of living strings with a certain length in the magical world.

 

Implement each required function by referring to the following API description.

※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.

 

The following is the description of API to be written in the User Code.

void init(int N)

This function is called in the beginning of each test case.
This function gives the maximum length of a string generated in the test case.

 

Parameters

   N : The maximum length of string that is generated within the test case (5 ≤ N ≤ 10)

int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[])

This function generates a string at mTimestamp.
This function makes all strings that are to die at the death time die. Then, it generates a string.
A string is given as mStr array. Its length and lifespan are given as mLen and mLifespan, respectively.
A string consists of only lowercase letters and ends with ‘＼0’.
A string that is identical to the previously given one can be given but the two are deemed different.
After the creation of a string, this function returns the number of living strings that are of the same length with the generated string.

 

The generated string finds friends following the rules.
Then, it also befriends the friends of the friends that are found.
In addition, it changes the death times of the befriended strings
so that they become the same as its own.
Please note that the death time can be later or earlier than the death time before the change.

 

 

Parameters

   mTimestamp: The time a function is called (1 ≤ mTimestamp ≤ 100,000)

   mLifespan: The lifespan of string (1 ≤ mLifespan ≤ 20)
   mLen: The length of generated string (5 ≤ mLen ≤ N)

   mStr: The generated string

 

Return

  The number of living strings whose length is mLen

int checkString(int mTimestamp, int mLen)

This function returns the number of living strings whose length is mLen at mTimestamp.

This function calculates the number of living strings after the strings destined to die at death time die.

 

Parameters

   mTimestamp: The time of function call (1 ≤ mTimestamp ≤ 100,000)
   mLen: The length of strings to be checked (5 ≤ mLen ≤ N)

 

Return

  The number of living strings whose length is mLen

 

[Example]

Below shows test case 1 from the beginning in order.

Order

Function

Return

Figure

1

init(7)

 

 

2

checkString(1, 5)

0

 

3

generateString(2, 4, 6, "member")

1

[Fig. 1] (a)

4

generateString(4, 5, 6, "barber")

2

[Fig. 1] (b)

5

generateString(6, 5, 6, "memory")

3

[Fig. 1] (c)

6

generateString(8, 10, 7, "carguer")

1

[Fig. 2] (a)

7

generateString(10, 5, 7, "embargo")

2

[Fig. 2] (b)

8

checkString(14, 6)

3

 

9

generateString(15, 2, 6, "langue")

1

 

10

checkString(16, 7)

0

 

 

Order 1 informs that the string generated in this test case has 7 letters at most.

Order 2 requests the number of living strings whose length is 5.
As there are NO strings formed, return 0.

 


                                                      [Fig. 1]

In Order 3, String “member” is generated. The death time of the string is 6. – Refer to (a) of Fig. 1
Return 1, the number of living strings whose length is 6.

In Order 4, String “barber” is generated. The death time of the string is 9.
“ber”, a substring, is both in the generated string and “member”. Thus, the two become friends.
The death time of “member” that became friends with “barber” is changed and becomes the same as that of “barber”. – Refer to (b) of Fig. 1
Return 2, the number of living strings whose length is 6.

In Order 5, String “memory” is generated. The string dies at Time 11.
“mem”, a substring, is both in the generated string and “member”. Thus, the two become friends.
As “barber” is a friend of “member”, it also become friends with “memory”.
Thus, the death times of the two strings that became friends with “memory” are changed and become the same as that of “memory”. – Refer to (c) of Fig. 1
Return 3, the number of living strings whose length is 6.

 


                                                [Fig. 2]

 

In Order 6, String “carguer” is generated. The string dies at Time 18.
Among the strings alive, there are NO strings with the same substring of at least 3 letters as the string.
In other words, there are NO strings with whom it can be friends. – Refer to (a) of Fig. 2
Return 1, the number of living strings whose length is 7.

In Order 7, String “embargo” is generated. The string dies at Time 15.
“bar”, a substring, is both in the generated string and “barber”. Thus, the two become friends.
Friends of “barber” become friends with “embargo”.
In addition, “arg”, a substring, is both in the generated string and “carguer”. Thus, the two become friends.
As “embargo” became friends with “barber” and “carguer”, “barber” and “carguer” also become friends.
(Friends of a friend become each other’s friends.)
The death times of the befriended strings will be the same as the death time of “embargo”. – Refer to (b) of Fig. 2
Please note that the death time of “carguer” decreased from 18 to 15.
Return 2, the number of living strings whose length is 7.

In Order 8, the total number of living strings whose length is 6 is 3.

In Order 9, as the time is 15, all strings whose death time is 15 disappear.
String “langue” is generated and the string dies at Time 17.
“gue”, a substring, is both in the generated string and “carguer”.
However, as “carguer” died already, a friendship cannot be built between the two.
Return 1, the number of living strings whose length is 6.

In Order 10, as strings whose length is 7 all died, return 0.

 

11

generateString(21, 5, 6, "banana")

1

[Fig. 3] (a)

12

generateString(25, 5, 6, "banana")

2

[Fig. 3] (b)

13

generateString(29, 2, 6, "banana")

3

[Fig. 3] (c)

14

checkString(30, 6)

3

 

15

generateString(31, 2, 6, "banana")

1

 

 

 


                                                      [Fig. 3]

 

In Order 11, String “banana” is generated. The string dies at Time 26.
At Time 21 when it is generated, all other strings have died.
Thus, the number of strings whose length is 6 is 1.

In Order 12, String “banana” is generated. The string dies at Time 30.
Although there is already a string whose name is the same with it, the two are deemed different.
Thus, as there is a substring of at least the same 3 letters in both of them, they become friends.
Then, change the death time of the other “banana”. – Refer to (b) of Fig. 3
The number of strings whose length is 6 is 2.

In Order 13 as well, change all the death times of “banana” strings into 31. – Refer to (c) of Fig. 3
The number of strings whose length is 6 is 3.

In Order 14, as all “banana” strings are alive at Time 30, the number of strings whose length is 6 becomes 3.

In Order 15, all of the three “banana”s die and a new String “banana” is generated.
Thus, the number of strings whose length is 6 is 1.

 

16

generateString(33, 2, 5, "aacbb")

1

 

17

generateString(34, 2, 6, "aaccbb")

1

 

18

generateString(35, 2, 7, "aacxcbb")

1

 

19

checkString(36, 6)

1

 

20

checkString(37, 6)

0

 

 

When processing from Order 16 to Order 18, the generated strings all have substrings of “aac” and “cbb”.
Thus, they all become friends and the death time of the three strings becomes Time 37.
In Order 20, all of them die at Time 37. Thus, the number of strings whose length is 6 becomes 0.

 

[Constraints]

1. init() is called in the beginning of each test case.
2. For each test case, mTimestamp increases every time a function is called.
3. For each test case, the total sum of function call of generateString() and checkString() is 11,000 at most.
 

[Input and Output]

As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.

The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.


#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
#define maxN 11001
using namespace std;
 
 
int cnt[6];
int curT;
class node 
{
public:
    //int id;
    char s[10];
    int lengS;
    int timeDie;
    node *root;
    bool isDel;
    int lengCnt[6];
     
    void add(int mTimestamp, int mLen, char mStr[])
    {
         
        timeDie = mTimestamp;
        lengS = mLen;
        for(int i=0;i<=mLen;i++)s[i] = mStr[i];//<=
        isDel = false;
        for(int i=0;i<6;i++)lengCnt[i]=0;
        lengCnt[mLen - 5] =1;
        //cout<<cnt[mLen - 5]<<" ";
        cnt[mLen - 5] +=1;
        //cout<<mLen<<" cong thanh "<<cnt[mLen - 5]<<"\n";
        root = nullptr;
    }
 
    void merge(node *u)
    {
        for(int i=0;i<6;i++)lengCnt[i]+= u->lengCnt[i];
    }
 
    void destroy()
    {
         
         
        isDel = true;
        if(root != nullptr)return;
        else
        for(int i = 0;i< 6;i++) cnt[i]-= lengCnt[i];
    }
};
int numNode;
node a[11001];
class cmp
{
public:
    bool operator()(const node *n1, const node *n2)
    {
        return n1->timeDie > n2->timeDie;
    }
 
};
unordered_map <int, node *> dd;
priority_queue< node*, vector< node*>, cmp> pq;
node *findRoot(node *cur)
{
    while (cur->root != nullptr)
    {
        cur = cur->root;
    }
    return cur;
}
 
 
void init(int N)
{
    numNode = 0;
    curT =0;
    for(int i=0;i<6;i++)cnt[i]=0;
    while(pq.size()>0)pq.pop();
    dd.clear();
}
  
void connect( node *u, node *v)
{
    node *other = findRoot(v);
    if(other == u) return;else
    {   
        u->merge(v);
    other->root = u;
    }
}
 void destroyAll()
 {
     while(pq.size()>0)
     {
         node *newN = pq.top();
         if(newN->root ==nullptr && newN->timeDie > curT)break;
         newN->destroy();
         pq.pop();
     }
 }
int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[])
{
    //for(int i=0;i<6;i++)cout<<cnt[i]<<" ";cout<<"\n";
    curT = mTimestamp;
    destroyAll();
    node *newNode = &a[++numNode];
    newNode->add(mTimestamp + mLifespan , mLen, mStr);
    for(int i=0;i<= mLen - 3; i++)
    {
        int ret = 0;
        for(int j=0;j<3;j++)ret = ret*26 + mStr[i+j]-'a';
        if(dd.find(ret) != dd.end())
        {
             
            node *other = findRoot(dd[ret]);
            if(!other->isDel )
                {
                    //cout<<"ok\n";
                    connect(newNode, other);
                     
            }
             
        }
    }
     for (int i = 0; i <= mLen - 3; i++)
    {
       int ret = 0;
        for(int j=0;j<3;j++)ret = ret*26 + mStr[i+j]-'a';
        dd[ret] = newNode;
    }
    pq.push(newNode);
    return cnt[mLen - 5];
}
 
int checkString(int mTimestamp, int mLen)
{
    //for(int i=0;i<6;i++)cout<<cnt[i]<<" ";cout<<"\n";
    curT = mTimestamp;
    destroyAll();
    return cnt[mLen - 5];
}