Dynasties
National Olympiad — Regional round
Submission name: dynasty.cpp
Problem summary
Records contain a father and son. Duplicate records are allowed; cycles are absent. If a son is assigned conflicting fathers, output the first son whose conflict is detected while scanning the records. Otherwise find the person with the deepest chain of descendants, breaking ties by lexicographically largest name.
Input
The record count, followed by that many father–son name pairs.
Output
The conflicting son’s name, or the person with the most descendant generations and the required tie-break.
Constraints
At most 10,000 records; names have at most 5 lowercase Latin letters; descendant depth ≤100.
Worked example
An independently prepared example for this explanation.
Input
4 a b b c x y y z
Output
x
Solution analysis
- Map names to vertex IDs and remember each son’s father. Ignore exact duplicate records.
- On the first different father for an already-known son, output that son immediately.
- Otherwise the graph is a forest directed from parent to child. Obtain a topological order.
- Process that order backward: height[parent]=max(height[parent],height[child]+1). Pick maximum height, then greatest name.
Why it works
Each valid person has at most one parent and the input is acyclic, so the graph is a forest. Processing children before parents evaluates every descendant-chain height correctly. Comparing height/name pairs implements the required tie-break.
Watch out. Do not count an exact duplicate record as another child or as a conflict. Compare generations along one longest chain, not total descendants.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each valid person has at most one parent and the input is acyclic, so the graph is a
// forest. Processing children before parents evaluates every descendant-chain height correctly.
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;
int main(){
int records;
cin>>records;
unordered_map<string,int>id;
vector<string>name;
vector<vector<int>>g;
vector<int>father;
auto getID=[&](const string&s){
auto it=id.find(s);
if(it!=id.end()){
return it->second;
}
int v=(int)name.size();
id[s]=v;
name.push_back(s);
g.push_back({});
father.push_back(-1);
return v;
};
while(records--){
string a,b;
cin>>a>>b;
int u=getID(a),v=getID(b);
if(father[v]!=-1&&father[v]!=u){
cout<<b<<'\n';
return 0;
}
if(father[v]==-1){
father[v]=u;
g[u].push_back(v);
}
}
int n=(int)name.size();
if(!n){
return 0;
}
vector<int>in(n),order,height(n);
queue<int>q;
for(int v=0;v<n;++v){
in[v]=(father[v]!=-1);
if(!in[v]){
q.push(v);
}
}
while(!q.empty()){
int v=q.front();
q.pop();
order.push_back(v);
for(int u:g[v]){
if(--in[u]==0){
q.push(u);
}
}
}
for(int i=(int)order.size()-1;i>=0;--i){
int v=order[i];
for(int u:g[v]){
height[v]=max(height[v],height[u]+1);
}
}
int best=0;
for(int v=1;v<n;++v){
if(height[v]>height[best]||(height[v]==height[best]&&name[v]>name[best])){
best=v;
}
}
cout<<name[best]<<'\n';
}