Problem Analysis

Given N people with known gender (F for female, M for male), each person provides direct distance measurements to their friends. The distance between any two people is the minimum possible distance through any path of known relationships. For each person i, define their "opposite-gender distance" as the maximum value of D[i][j] where j belongs to the opposite gender. The person with the smallest opposite-gender distence is the "most popular" in their gender category.

Solution Approach

The core problem is computing shortest paths between all pairs of people. Since direct measurements only cover some relationships, we need to propagate distances through intermedaite people. The Floyd-Warshall algorithm efficiently computes all-pairs shortest paths in O(N³) time, which is sufficient for N ≤ 500.

Implementation

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 505;
const int INFINITY = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int personCount;
    cin >> personCount;
    
    vector<vector<int>> shortest(personCount + 1, vector<int>(personCount + 1, INFINITY));
    vector<char> gender(personCount + 1);
    
    for (int i = 1; i <= personCount; i++) {
        shortest[i][i] = 0;
        int relationCount;
        cin >> gender[i] >> relationCount;
        
        for (int k = 0; k < relationCount; k++) {
            int friendId, distance;
            scanf("%d:%d", &friendId, &distance);
            shortest[i][friendId] = distance;
        }
    }
    
    for (int middle = 1; middle <= personCount; middle++) {
        for (int start = 1; start <= personCount; start++) {
            for (int end = 1; end <= personCount; end++) {
                if (shortest[start][middle] + shortest[middle][end] < shortest[start][end]) {
                    shortest[start][end] = shortest[start][middle] + shortest[middle][end];
                }
            }
        }
    }
    
    vector<int> maxOppositeDist(personCount + 1, 0);
    
    for (int i = 1; i <= personCount; i++) {
        for (int j = 1; j <= personCount; j++) {
            if (gender[i] != gender[j] && shortest[i][j] < INFINITY) {
                maxOppositeDist[j] = max(maxOppositeDist[j], shortest[i][j]);
            }
        }
    }
    
    int minFemaleDist = INFINITY, minMaleDist = INFINITY;
    
    for (int i = 1; i <= personCount; i++) {
        if (gender[i] == 'F') {
            minFemaleDist = min(minFemaleDist, maxOppositeDist[i]);
        } else {
            minMaleDist = min(minMaleDist, maxOppositeDist[i]);
        }
    }
    
    bool firstOutput = true;
    for (int i = 1; i <= personCount; i++) {
        if (gender[i] == 'F' && maxOppositeDist[i] == minFemaleDist) {
            if (!firstOutput) cout << " ";
            cout << i;
            firstOutput = false;
        }
    }
    cout << "\n";
    
    firstOutput = true;
    for (int i = 1; i <= personCount; i++) {
        if (gender[i] == 'M' && maxOppositeDist[i] == minMaleDist) {
            if (!firstOutput) cout << " ";
            cout << i;
            firstOutput = false;
        }
    }
    cout << "\n";
    
    return 0;
}

Key Points

1. Initialization: Set dist[i][i] = 0 for all i, and dist[i][j] = INF for all other pairs.

2. Floyd-Warshall: For each middle vertex k, check if going through k provides a shorter path between i and j. The formula is:

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
   

3. Computing Maximum Opposite-Gender Distance: After obtaining all shortest paths, for each person j, find the maximum distance from any person i of the opposite gender. This represents how "unreachable" j is to the opposite gender.

4. Finding Winners: A smaller maximum opposite-gender distance means the person is more reachable by the opposite gender, hence more "popular." Select all people whose maximum distance equals the minimum among their gender group.

The algorithm runs in O(N³) time and O(N²) space, wich easily satisfies the constraint N ≤ 500.