Subtask 1

For the first subtask, we can use a bitmask technique to iterate through all ~2^N~ possible boolean assignments, and check in ~\mathcal{O}(N + M)~ time if all requirements are met. To determine the actual solution, consider the bitwise ~and~ of all masks where the requirements are met. If the ~i^{th}~ bit is ~1~, then ~i^{th}~ student must go on the trip. Now consider the bitwise ~or~ of all masks where the requirements are met. If the ~i^{th}~ bit is ~0~, then ~i^{th}~ student must not go on the trip. All other students are indeterminate.

Time Complexity: ~\mathcal{O}(2^N \cdot (N + M))~

Subtask 2

For the second subtask, consider a graph with students as vertices and requirements as edges. Note that at most one vertex of each edge can be selected. Here, it is sufficient to determine if the graph is bipartite, which can be done with a breadth first search. Note that there will never be a way to determine for sure if a student is going on the trip with ~K = 0~ for this subtask.

Time Complexity: ~\mathcal{O}(N + M)~

Subtask 3

For the third subtask, we can create the graph the same way for PARTNERS requirements. For FRIENDS requirements, since both students must be assigned the same value, we can merge the two vertices into a single vertex (using union find) before performing the bipartite check. Finally, we must check if there is a boolean assignment to the bipartite graph such that all students who must go on the trip are on the same side. From each student that must go on the trip, we will perform a depth first search on the graph and assign boolean values based on the parity of the current depth. Once this is done, if there are any contradictions in the value assignment, then there is no solution. Otherwise, we can determine the answer by looking at the assigned value for each student (with students with no assigned value being indeterminate).

Time Complexity: ~\mathcal{O}(N + M \cdot \alpha(N))~

Subtask 4

For the fourth subtask, the question is very similar to the 2-SAT problem. Each requirement can be reduced to conjunctive normal form (including the requirement that a student must go on the trip). From here, we can create an implication graph and compute the strongly connected components of the graph in ~\mathcal{O}(N + M)~ time. As long as affirmative and negative vertices in the implication graph are not in the same strongly connected component, then the requirements can all be met.

To determine the actual solution, recall that in the implication graph, all vertices in the same strongly connected component must have the same boolean value. A directed edge from ~a~ to ~b~ means that if ~a~ is true, then ~b~ must also be true. Since the affirmative and negative vertices cannot be the same value, if one is reachable from the other, then the first must be assigned false, and the second must be assigned true. This can be done with a depth first or breadth first search for each student. This takes ~\mathcal{O}(N \cdot (N + M))~ time in total.

Next, we will mark the strongly connected component of the affirmative vertices of students that must go on the trip as true. and mark the strongly connected component of the negative vertices of students that must go on the trip as false. As long as there is a solution, this should not contradict the previous assignments. All vertices that are reachable from a vertex assigned true, must also be true, and all vertices that can reach a false vertex must also be false. However, a useful property of implication graphs is that it is skew-symmetric. This means that for some literals ~x~ and ~y~ (which may or may not contain negations), if there is a path from ~x~ to ~y~, then there is a path from ~\neg y~ to ~\neg x~. Proof is left as an exercise for the reader. Thus, if ~y~ is reachable from ~x~, then ~\neg x~ is reachable from ~\neg y~. It follows that if ~x~ is reachable from ~\neg x~ (meaning ~x~ is true), then ~y~ is reachable from ~\neg y~ (meaning ~y~ is also true). So checking the condition in the previous paragraph suffices and this paragraph can be ignored (thank you Dormi).

Once this is done, it should be the case for all vertices that if either the affirmative or negative vertex of a student is assigned a value, the other vertex has the opposite value. All other vertices cannot have their value determined.

Alternatively, the standard 2-SAT algorithm can first be run on the initial implication graph to determine if all the requirements can be met. Then for each person, we will create a new graph formed by the initial graph, with the added constraint that the student must go on the trip. The same can be done for the constraint that the student must not go on the trip. If both can be satisfied, then it cannot be determined if the student can go on the trip or not. Otherwise, the answer will be whichever constraint allowed the trip requirements to be met.

Time Complexity: ~\mathcal{O}(N \cdot (N + M))~

Subtask 5

For the fifth subtask, we will use the same idea as the fourth subtask, however instead of performing a depth first or breadth first search to determine if the affirmative and negative vertices are reachable from each other, we will instead compute the transitive closure of the directed acyclic graph formed by the strongly connected components. If we use a 2D boolean array to store the transitive closure (where each boolean takes 1 byte), and assume ~N = 25\,000~ (which means the directed acyclic graph will have ~50\,000~ vertices in the worst case), then this will take around 2.5 GB of memory, which exceeds the memory limit. Note that even though a boolean takes up 1 byte, we cannot manipulate the individual bits, wasting space. To reduce our memory usage, we will use a bitset instead, which will allow us to modify each of the 8 bits in a byte. This will take around 313 MB of memory, well within the memory limit.

From here, we can use dynamic programming on the directed acyclic graph to determine the components that are reachable from each other. For each component, we will compute the bitwise ~or~ of all the bitsets of adjacent components, as well as the bitset of the current component. Now, the ~j^{th}~ bit of the ~i^{th}~ bitset will be ~1~ if and only if component ~j~ is reachable from component ~i~.

Time Complexity: ~\mathcal{O}(N \cdot (N + M))~ (with a really good constant)