brevoptimering

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

void insertion_sort(vector<int>& arr, int length) {
    int j, temp;
    for (int i = 0; i < length; i++) {
        j = i;

        while (j > 0 && arr[j] < arr[j - 1]) {
            temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
            j--;
        }
    }
}

class Person {
public:
    vector<double> ip;
    bool done;
    int nmr;
    int ant;
    int m;
private:

};

int main() {
    int pers;
    vector<int> aPers;
    vector<vector<int>> prc;
    vector<vector<int>> to;
    vector<Person> inf;
    queue<int> q;
    cin >> pers;
    prc.resize(pers);
    to.resize(pers);
    for (int i = 0; i < pers; i++) {
        Person p;
        inf.push_back(p);
        int tmp = 0;
        cin >> tmp;
        aPers.push_back(tmp);
        tmp = 0;
        cin >> tmp;
        int lp = tmp;
        if (tmp == 0) {

        } else {
            for (int j = 0; j < lp; j++) {
                tmp = 0;
                cin >> tmp;
                to[i].push_back(tmp);
                tmp = 0;
                cin >> tmp;
                prc[i].push_back(tmp);
            }
        }

    }
    for (int i = 0; i < pers; i++) {
        inf[i].m = aPers[i];
        inf[i].nmr = i;
        inf[i].done = false;
        for (int j = 0; j < to[i].size(); j++) {
            inf[to[i][j] - 1].ant++;
        }
    }
    for (int i = 0; i < inf.size(); i++) {
        if (inf[i].ant == 0) {
            q.push(i);
        }
    }
    int antal = 0;
    vector<int> op;
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (inf[p].ant == 0 && inf[p].done == false) {
            if (inf[p].ip.size() == 0) {
                for (int j = 0; j < to[p].size(); j++) {
                    inf[to[p][j] - 1].ip.push_back(inf[p].m * prc[p][j] * 0.01);
                    inf[to[p][j] - 1].ant--;
                    if (inf[to[p][j] - 1].ant == 0) {
                        q.push(to[p][j] - 1);
                    }
                }
            } else {
                double realM = 0;
                for (int i = 0; i < inf[p].ip.size(); i++) {
                    realM += inf[p].ip[i];
                }
                if (realM > inf[p].m) {
                    for (int j = 0; j < to[p].size(); j++) {
                        inf[to[p][j] - 1].ip.push_back(inf[p].m * prc[p][j] * 0.01);
                        inf[to[p][j] - 1].ant--;
                        if (inf[to[p][j] - 1].ant == 0) {
                            q.push(to[p][j] - 1);
                        }
                    }
                } else {
                    for (int j = 0; j < to[p].size(); j++) {
                        inf[to[p][j] - 1].ip.push_back(realM *prc[p][j] * 0.01);
                        inf[to[p][j] - 1].ant--;
                        if (inf[to[p][j] - 1].ant == 0) {
                            q.push(to[p][j] - 1);
                        }
                    }
                }
            }

        }
        if (inf[p].ant == 0) {
            inf[p].done = true;
            if (inf[p].ip.size() == 0) {
                op.push_back(p + 1);
            } else {
                double tmp = 0;
                for (int j = 0; j < inf[p].ip.size(); j++) {
                    tmp += inf[p].ip[j];
                }
                if (inf[p].m <= tmp) {
                    op.push_back(p + 1);
                }
            }

        }
        antal++;
    }
    insertion_sort(op, op.size());
    for (int i = 0; i < op.size(); i++) {
        cout << op[i] << " ";
    }

#ifdef _DEBUG
    system("pause");
#endif // _DEBUG

}