IOI Walls

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;
using std::pair;

// https://dmoj.ca/problem/ioi00p4 (input ommitted due to length)
int main() {
    int region_num;
    int town_num;
    int member_num;
    std::cin >> region_num >> town_num >> member_num;

    vector<int> members(member_num);
    for (int& m : members) {
        std::cin >> m;
        m--;
    }
    vector<vector<int>> town_regions(region_num);
    vector<vector<pair<int, int>>> regions(region_num);
    for (int r = 0; r < region_num; r++) {
        int border_num;
        std::cin >> border_num;
        vector<int> towns(border_num);
        for (int& t : towns) {
            std::cin >> t;
            t--;
            town_regions[t].push_back(r);
        }
        for (int t = 0; t < border_num; t++) {
            regions[r].push_back({towns[t], towns[(t + 1) % border_num]});
        }
    }

    std::map<pair<int, int>, int> prev_walls;
    vector<vector<int>> neighbors(region_num);
    for (int r = 0; r < region_num; r++) {
        for (const pair<int, int>& w : regions[r]) {
            if (prev_walls.count(w)) {
                // dupes might happen but that doesn't really matter
                neighbors[r].push_back(prev_walls[w]);
                neighbors[prev_walls[w]].push_back(r);
            } else {
                prev_walls[w] = r;
                pair<int, int> reverse{w.second, w.first};
                prev_walls[reverse] = r;
            }
        }
    }

    vector<vector<int>> min_crossings(region_num, vector<int>(region_num));
    for (int start = 0; start < region_num; start++) {
        int moves = 0;
        vector<bool> visited(region_num);
        vector<int> frontier{start};
        visited[start] = true;
        while (!frontier.empty()) {
            vector<int> in_line;
            moves++;
            for (int r : frontier) {
                for (int n : neighbors[r]) {
                    if (!visited[n]) {
                        min_crossings[start][n] = moves;
                        visited[n] = true;
                        in_line.push_back(n);
                    }
                }
            }
            frontier = in_line;
        }
    }

    int min_crossing_sum = INT32_MAX;
    int best_region = -1;
    for (int meeting = 0; meeting < region_num; meeting++) {
        int this_min_cross = 0;
        for (int m : members) {
            int m_min_crossings = INT32_MAX;
            for (int t : town_regions[m]) {
                m_min_crossings = std::min(m_min_crossings, min_crossings[t][meeting]);
            }
            this_min_cross += m_min_crossings;
        }
        if (this_min_cross < min_crossing_sum) {
            min_crossing_sum = this_min_cross;
            best_region = meeting;
        }
    }
    cout << min_crossing_sum << endl << best_region + 1 << endl;
}