Wesley's Anger Contest 1 Problem 5 - Rule of Four

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 3.0s
Java 5.0s
Memory limit: 512M

Author:
Problem types

Your school has decided to organize a research trip for a class of N students numbered from 1 to N. Unfortunately, organizing trips are not easy as it seems, as there are M rules that need to be followed in order for the trip to happen. The rules come in four different forms:

Input Format Description
FRIENDS a b Students a and b are friends and either they both go on the trip, or they both do not go on the trip
ENEMIES a b Students a and b are enemies and at most one of them can go on the trip
PARTNERS a b Students a and b are research partners and the lab instructor would like exactly one of them to go on the trip
GROUP a b Students a and b are in a study group and at least one of them should go on the trip

In addition, there are K students who must go on the trip no matter what. Can you determine if the school trip will happen? The trip will only happen if all the rules are followed.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask Points N, M, K Additional Constraints
1 5\% 1 \le N \le 16
0 \le M \le 32
0 \le K \le N
None
2 10\% 1 \le N \le 25\,000
0 \le M \le 50\,000
K = 0
All rules will be PARTNERS rules
3 10\% 1 \le N \le 25\,000
0 \le M \le 50\,000
0 \le K \le N
All rules will be FRIENDS or PARTNERS rules
4 35\% 1 \le N \le 500
0 \le M \le 1\,000
0 \le K \le N
None
5 40\% 1 \le N \le 25\,000
0 \le M \le 50\,000
0 \le K \le N
None

For all subtasks:

1 \le a_i, b_i \le N

a_i \neq b_i

Input Specification

The first line contains 3 integers, N, M, and K.

The next K lines contain the numbers of the students who must go on the trip. Each line contains a single integer between 1 and N. It is guaranteed that these integers are pairwise distinct.

The next M lines describe the rules. Each line will be in the format specified above. Specifically, each line will contain the name of the rule, followed by 2 integers a_i and b_i, describing the students the rule applies to.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output YES if all the rules are followed and the school trip happens and NO otherwise.

If and only if the answer is YES, on the next line, print a string of N characters, consisting of only 0s, 1s, and ?s. If the i^{th} student is definitely going on the trip, then the i^{th} character is 1. If the i^{th} student is definitely not going on the trip, then the i^{th} character is 0. Otherwise, if it cannot be determined whether the i^{th} is going on the trip or not, then the i^{th} character is ?.

If (and only if) the answer is NO, then do not print anything else.

Sample Input 1

3 3 1
1
GROUP 1 2
GROUP 1 3
ENEMIES 2 3

Sample Output 1

YES
1??

Sample Explanation 1

Student 1 must attend the trip. Either student 2 or student 3 can attend the trip (but not both), though it cannot be determined which one will be attending.

Sample Input 2

4 3 0
PARTNERS 1 2
PARTNERS 1 3
PARTNERS 4 2

Sample Output 2

YES
????

Sample Explanation 2

Either students 1 and 4 will attend the trip, or students 2 and 3 will attend the trip, but it cannot be determined which two will be attending.

Sample Input 3

3 3 0
PARTNERS 1 2
PARTNERS 1 3
PARTNERS 3 2

Sample Output 3

NO

Sample Input 4

4 6 1
4
PARTNERS 1 3
PARTNERS 3 4
PARTNERS 4 2
PARTNERS 2 1
FRIENDS 2 3
FRIENDS 4 1

Sample Output 4

YES
1001

Sample Explanation 4

For all students, it can be determined for sure whether they will attend the trip or not.


Comments

There are no comments at the moment.