USACO 2.3 Controlling Companies

This is a search problem that can be solved using brutal force DFS. We first have a pass to initialize the states of companies’ controlling states by bootstrapping controlling companies and controlled companies, and also gather company share statistics for each companies. Then we have a second pass to update the global control state where for each company A, if it controls company B (initialized in first pass by calculating if A has over 50% shares of B), then A should also have same number shares for each company C that company B has shares in. This process continues and the global state should converge and reach a fixed state, as for each company, we will do DFS for every other company only once.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <unordered_map>
#include <set>
#include <stack>

using namespace std;

int N;
const int C = 100;

int main() {
    ifstream fin("concom.in");
    ofstream fout("concom.out");
    fin >> N;
    vector<vector<pair<int, int>>> nodes(C + 1, vector<pair<int,int>>(0));
    int f, c, p;
    for (int i = 0; i < N; ++i) {
        fin >> f >> c >> p;
        nodes[f].push_back(make_pair(c, p));
    }
    
    vector<unordered_map<int, int>> map(C + 1, unordered_map<int, int>());
    vector<set<int>> result(C + 1, set<int>());
    vector<bool> visited(C + 1, false);
    
    for (int i = 1; i <= C; ++i) {
        for (auto &pair : nodes[i]) {
            map[i][pair.first] += pair.second;
            if (pair.second <= 50) {
                continue;
            }
            result[i].insert(pair.first);
        }
    }
    
    for (int i = 1; i <= C; ++i) {
        std::fill(visited.begin(), visited.end(), false);
        stack<int> s;
        for (auto &c : result[i]) {
            s.push(c);
        }
        while (!s.empty()) {
            int c = s.top();
            s.pop();
            if (visited[c]) continue;
            for (auto &cc : nodes[c]) {
                map[i][cc.first] += cc.second;
                if (map[i][cc.first] > 50) {
                    result[i].insert(cc.first);
                    s.push(cc.first);
                }
            }
            visited[c] = true;
        }
    }
    
    for (int i = 1; i <= C; ++i) {
        if (result[i].empty()) continue;
        for (auto iter = result[i].begin(); iter != result[i].end(); ++iter) {
            if (i == *iter) continue;
            fout << i << " " << *iter << endl;
        }
    }
}