Hello, Codeforces!

Since some of you have been wanting me to publish the algorithm from my previous blog, I have decided to make it public today, for once and for all.

**** Disclaimer: this algorithm is extremely complex and may make your brain explode. Read with caution. ****

In short, we can divide the task of getting a girlfriend in 3 steps:

1. talk to a girl
2. get lucky
3. get a girlfriend

For simplicity's sake we will skim over part one and explain it later. Now to get lucky you simply have to talk to many girls (assuming you know how to talk to one). This can be easily done with randomization. First, of course, the state of you and a random girl can be represented with a graph with each edges representing your action. We simply run djikstra to find the shortest path between the state of you being single and them being your girlfriend. Of course this graph has negative weights so simply running Djikstra would not work as you would be stuck in an infinite loop and never get a girl (like all of you who spends way too much time contemplating how to talk to girls but never actually approach them). To solve the negative edge weights, one can use floyd warshall or johnson's algorithm, but that takes way too long and even djikstra on positive edge weight graph takes too long. Thus, we will employ a greedy strategy.

Basically, define an edge that is a maximum (minimum time, maximum effectiveness) outward edge of each node as "rizz". We will continually try "rizzing" and hope that you will eventually get to the state of "dating", which is when the two of you become bf-gf (for all my coders who dont know what dating is). Magically, this allows each node to have only one outward edge, creating a functional graph which is basically a tree. So now we use a link cut tree, along with a static top tree to maintain these states instead.

Some of you may wonder why not just maintain a tree? well the answer is simple. "Rizzing" or the best edge changes over time. Each edge can be modified as a straight line of a time function, which allows use to maintain a CHT on the static top tree and link cut trees to find the optimal path. Using link cut trees you can continually splay her heart through continually rizzing, eventually reaching the top of her priority queue. Note that this part is trivial compared to "talking to girls" so we will simply assume the reader knows how to do this to save time. Now this algorithm is only a greedy algorithm, and does not work all the time. But we can prove that it works with probability (1/72). Proof is again ommited as excercise for the reader as this is, again, trivial compared to part 1. Now, to change ur tree structure from person to person, all we have to do is encode the tree as bitmasks and use a revolutionary bitset that can instrically represent static top trees, link cut trees, CHT, and lichao trees to maintain the state, and apply lazy operations to make sure each time we try "rizzing", the amortized cost is only O(1). Thus, on average you are expected to get a girl in O(72) from some maths.

Now the hard part, "How to talk to girls". Well this part is extremely difficult to do, even as an expert in the field. I have another algorithm and proof of its correctness, but it is simply too long to fit in a codeforces blog.

Warning on Implementation: Do not forget to clear your bitset with lazy clear operation between conversations. Failing to reset your bitset from your "ex" will cause a massive runtime collision, resulting in a critical System Test Failed verdict.

Wish you the best of luck in implementing this algorithm! Please O72 in the comments to receive good luck from The Master(s) of Rizz.