Proficient.
Put your skills to the test.

Problem summary

Student 1 creates a new song whenever he attends a contest; only that new song is sung there. At a contest without him, attendees sing and learn the union of all songs they already know. Find which other students know every song by the end.

Constraints

3≤M≤2000; 5≤N≤2000; 2≤B≤N/2.

Worked example

An independently prepared example for this explanation.

3 6
3 1 2 3
3 4 1 5
2 2 4

2
2 4

Solution analysis

1. Represent each student’s known songs by a bitset with one bit per contest. When student 1 attends, assign a new bit and set it for every attendee; earlier songs are not exchanged on that occasion.
2. When student 1 is absent, OR together all attendee bitsets, then OR the resulting union into every attendee. A final bitset records every created song; compare each student numbered 2 through N with it.
3. The sample creates song one for students 1,2,3 and song two for 1,4,5. At the last contest, 2 and 4 exchange their songs, so those two colleagues know both. Student 1 is excluded from the requested list.

Why it works

Initially all knowledge sets are empty. A contest with the songwriter adds exactly its one new song to attendees. A contest without him makes precisely the attendees’ union known to each attendee. The bitset operations implement these rules exactly, so induction over chronological contests proves the final sets correct.

Watch out. Do not spread old songs at a contest with student 1. Student 1 is excluded. If no songs were created, every colleague vacuously knows all songs.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<cstdint>
#include<algorithm>
// Algorithm: Represent each student’s known songs by a bitset with one bit per contest.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int contests,students;
    cin>>contests>>students;
    int words=(contests+63)/64;
    vector<vector<uint64_t>>known(students+1,vector<uint64_t>(words,0));
    vector<uint64_t>allSongs(words,0);
    int songs=0;
    for(int event=0;event<contests;event++){
        int count;
        cin>>count;
        vector<int>attendees(count);
        bool songwriter=false;
        for(int&student:attendees){
            cin>>student;
            songwriter=songwriter||student==1;
        }
        if(songwriter){
            int word=songs/64;
            uint64_t bit=uint64_t(1)<<(songs%64);
            songs++;
            allSongs[word]|=bit;
            for(int student:attendees){
                known[student][word]|=bit;
            }
        }
        else{
            vector<uint64_t>shared(words,0);
            for(int student:attendees){
                for(int w=0;w<words;w++){
                    shared[w]|=known[student][w];
                }
            }
            for(int student:attendees){
                for(int w=0;w<words;w++){
                    known[student][w]|=shared[w];
                }
            }
        }
    }
    vector<int>answer;
    for(int student=2;student<=students;student++){
        if(known[student]==allSongs){
            answer.push_back(student);
        }
    }
    cout<<answer.size()<<'\n';
    if(!answer.empty()){
        for(size_t i=0;i<answer.size();i++){
            if(i!=0){
                cout<<' ';
            }
            cout<<answer[i];
        }
        cout<<'\n';
    }
}