Cultural Olympiad Teams
National Olympiad — National round (2020 season)
Submission name: olympiad.cpp
Problem summary
Each student knows one language and plays one instrument. A team may use each language and instrument at most once. Among all largest teams, classify students, languages, and instruments that occur always or never.
Input
N S T; N language-instrument pairs, in student order.
Output
Maximum team size and six classification counts; then six increasing index lists: always/never students, languages, instruments. Empty lists occupy empty lines.
Constraints
N ≤ 150,000; S,T ≤ 75,000; parallel student pairs are allowed.
Worked example
An independently prepared example for this explanation.
Input
6 4 5 1 1 2 1 3 2 3 3 3 4 4 4
Output
3 1 1 2 0 2 1 6 5 3 4 1 4 5
Solution analysis
- View students as distinct edges in a bipartite multigraph. Compute a maximum matching using Hopcroft–Karp, retaining edge identities because two students may have identical skills.
- Orient unmatched edges from language to instrument and matched edges in reverse. Find strongly connected components, vertices reachable from an unmatched language, and vertices that can reach an unmatched instrument. An edge can change membership exactly when its endpoints lie in one component, its language is reachable from a free language, or its instrument can reach a free instrument.
- A matched language is compulsory precisely when no free language can reach it; use the reverse condition for instruments. Only isolated skill vertices are never represented. In the example student 6 is fixed, student 5 is forbidden, languages 3 and 4 and instruments 1 and 4 are compulsory, and unused instrument 5 is never present.
Why it works
The symmetric difference of two maximum matchings splits into alternating cycles and even alternating paths. Directed cycles are exactly the strongly connected cases. Even paths move an unmatched vertex within one bipartition, giving the two free-vertex reachability cases. Conversely reversing any such cycle or path preserves matching size, so these conditions are both necessary and sufficient for edge flexibility and vertex coverage changes. Every nonisolated vertex can be matched in some maximum matching: if currently free, replace the edge incident to any matched neighbor.
Watch out. Do not merge parallel students. Maximum means largest cardinality, not merely locally maximal. Directed reachability for free instruments must use reversed edges.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,s,t;
cin>>n>>s>>t;
vector<int>left(n),right(n),matchL(s,-1),matchR(t,-1),distance(s),cursor(s);
vector<vector<int>>incident(s);
for(int i=0;i<n;i++){
cin>>left[i]>>right[i];
incident[--left[i]].push_back(i);
--right[i];
}
int size=0;
while(true){
queue<int>queue;
fill(distance.begin(),distance.end(),-1);
fill(cursor.begin(),cursor.end(),0);
for(int u=0;u<s;u++){
if(matchL[u]==-1){
distance[u]=0;
queue.push(u);
}
}
int shortest=s+1;
while(!queue.empty()){
int u=queue.front();
queue.pop();
if(distance[u]>=shortest){
continue;
}
for(int id:incident[u]){
int other=matchR[right[id]];
if(other==-1){
shortest=distance[u]+1;
}
else if(distance[left[other]]==-1){
distance[left[other]]=distance[u]+1;
queue.push(left[other]);
}
}
}
if(shortest==s+1){
break;
}
for(int root=0;root<s;root++){
if(matchL[root]!=-1||distance[root]!=0){
continue;
}
vector<int>path(1,root),chosen;
bool augmented=false;
while(!path.empty()&&!augmented){
int u=path.back();
bool advanced=false;
while(cursor[u]<int(incident[u].size())){
int id=incident[u][cursor[u]++];
int other=matchR[right[id]];
if(other==-1&&distance[u]+1==shortest){
chosen.push_back(id);
for(int e:chosen){
matchL[left[e]]=e;
matchR[right[e]]=e;
}
augmented=true;
size++;
break;
}
if(other!=-1&&distance[left[other]]==distance[u]+1){
chosen.push_back(id);
path.push_back(left[other]);
advanced=true;
break;
}
}
if(!advanced&&!augmented){
distance[u]=-1;
path.pop_back();
if(!chosen.empty()){
chosen.pop_back();
}
}
}
}
}
int vertices=s+t;
vector<vector<int>>graph(vertices),reverse(vertices);
for(int i=0;i<n;i++){
int u=left[i],v=s+right[i];
if(matchL[u]==i){
swap(u,v);
}
graph[u].push_back(v);
reverse[v].push_back(u);
}
vector<bool>seen(vertices);
vector<int>order,next(vertices);
for(int root=0;root<vertices;root++){
if(seen[root]){
continue;
}
vector<int>stack(1,root);
seen[root]=true;
while(!stack.empty()){
int u=stack.back();
if(next[u]==int(graph[u].size())){
order.push_back(u);
stack.pop_back();
}
else{
int v=graph[u][next[u]++];
if(!seen[v]){
seen[v]=true;
stack.push_back(v);
}
}
}
}
vector<int>component(vertices,-1);
int components=0;
for(auto it=order.rbegin();it!=order.rend();++it){
if(component[*it]!=-1){
continue;
}
vector<int>stack(1,*it);
component[*it]=components;
for(size_t j=0;j<stack.size();j++){
for(int v:reverse[stack[j]]){
if(component[v]==-1){
component[v]=components;
stack.push_back(v);
}
}
}
components++;
}
vector<bool>fromFree(vertices),toFree(vertices);
auto reach=[&](const vector<vector<int>>&edges,vector<bool>&reached,vector<int>seeds){
for(int u:seeds){
reached[u]=true;
}
for(size_t j=0;j<seeds.size();j++){
for(int v:edges[seeds[j]]){
if(!reached[v]){
reached[v]=true;
seeds.push_back(v);
}
}
}
};
vector<int>seeds;
for(int u=0;u<s;u++){
if(matchL[u]==-1){
seeds.push_back(u);
}
}
reach(graph,fromFree,seeds);
seeds.clear();
for(int v=0;v<t;v++){
if(matchR[v]==-1){
seeds.push_back(s+v);
}
}
reach(reverse,toFree,seeds);
vector<vector<int>>answer(6);
for(int i=0;i<n;i++){
int u=left[i],v=s+right[i];
// Alternating cycles and even paths describe every matching change.
bool flexible=component[u]==component[v]||fromFree[u]||toFree[v];
if(matchL[u]==i&&!flexible){
answer[0].push_back(i+1);
}
if(matchL[u]!=i&&!flexible){
answer[1].push_back(i+1);
}
}
for(int u=0;u<s;u++){
if(matchL[u]!=-1&&!fromFree[u]){
answer[2].push_back(u+1);
}
if(incident[u].empty()){
answer[3].push_back(u+1);
}
}
vector<int>degree(t);
for(int v:right){
degree[v]++;
}
for(int v=0;v<t;v++){
if(matchR[v]!=-1&&!toFree[s+v]){
answer[4].push_back(v+1);
}
if(degree[v]==0){
answer[5].push_back(v+1);
}
}
cout<<size;
for(const auto&list:answer){
cout<<' '<<list.size();
}
cout<<'\n';
for(const auto&list:answer){
for(size_t j=0;j<list.size();j++){
if(j>0){
cout<<' ';
}
cout<<list[j];
}
cout<<'\n';
}
}