Ryhmät

input/code.cpp: In function 'int main()':
input/code.cpp:87:37: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |         if (toiveet_voimassa.size() < koko) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <map>
 
using namespace std;

typedef pair<int, int> P;

struct Vaihe {
    int edellinen_vaihe;
    int ryhmän_koko;
    unordered_set<int> käytetyt;
    unordered_map<int, int> jatkot;
    bool onnistuu = false;
};

int main() {
    iostream::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> toiveet(n);
    for (int i = 0; i < n; i++) {
        cin >> toiveet[i].first >> toiveet[i].second;
    }
    sort(toiveet.begin(), toiveet.end());

    vector<vector<int>> testit(t);
    int ryhmien_määrä_yhteensä = 0;
    for (auto &testi : testit) {
        int ryhmien_määrä;
        cin >> ryhmien_määrä;
        testi.resize(ryhmien_määrä);
        for (int i = 0; i < ryhmien_määrä; i++) {
            cin >> testi[i];
        }
        sort(testi.begin(), testi.end());
        ryhmien_määrä_yhteensä += ryhmien_määrä;
    }

    // Tehdään graafi
    vector<int> vastausvaiheet;
    vector<Vaihe> vaiheet;
    //vaiheet.reserve(ryhmien_määrä_yhteensä + 1);
    vaiheet.push_back(Vaihe{-1, 0, {}, {}});
    vaiheet[0].onnistuu = true;
    for (auto& testi : testit) {
        int vaihe = 0;
        for (int koko : testi) {
            auto& jatkot = vaiheet[vaihe].jatkot;
            if (!jatkot.count(koko)) {
                jatkot[koko] = (int)vaiheet.size();
                vaiheet.push_back(Vaihe{vaihe, koko, {}, {}});
            }
            vaihe = jatkot[koko];
        }
        vastausvaiheet.push_back(vaihe);
    }

    set<P> seuraavat;
    for (auto& jatko : vaiheet[0].jatkot) {
        seuraavat.insert({jatko.first, jatko.second});
    }

    set<P> toiveet_voimassa;
    int toive_i = 0;

    while (!seuraavat.empty()) {
        int koko, vaihe_i;
        tie(koko, vaihe_i) = *seuraavat.begin();
        seuraavat.erase(seuraavat.begin());

        while (!toiveet_voimassa.empty() && toiveet_voimassa.begin()->first < koko) {
            toiveet_voimassa.erase(toiveet_voimassa.begin());
        }
        while (toive_i < n && toiveet[toive_i].first <= koko) {
            if (toiveet[toive_i].second >= koko) {
                toiveet_voimassa.insert({toiveet[toive_i].second, toive_i});
            }
            toive_i++;
        }
        if (toiveet_voimassa.size() < koko) {
            continue; // Tämä vaihe ei onnistu, jatkoja ei ole syytä tutkia.
        }

        auto& vaihe = vaiheet[vaihe_i];
        vaihe.käytetyt = vaiheet[vaihe.edellinen_vaihe].käytetyt;
        int puuttuu = koko;
        for (auto toive: toiveet_voimassa) {
            int toive_i = toive.second;
            if (vaihe.käytetyt.count(toive_i)) continue;
            vaihe.käytetyt.insert(toive_i);
            puuttuu--;
            if (puuttuu == 0) break;
        }
        if (puuttuu == 0) {
            vaihe.onnistuu = true;
            for (auto& jatko : vaihe.jatkot) {
                seuraavat.insert({jatko.first, jatko.second});
            }
        }
    }

    for (auto i: vastausvaiheet) {
        cout << (vaiheet[i].onnistuu ? "YES\n" : "NO\n");
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: RUNTIME ERROR

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: RUNTIME ERROR

Test 6

Group: 2

Verdict: RUNTIME ERROR

Test 7

Group: 2

Verdict: RUNTIME ERROR

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: RUNTIME ERROR

Test 11

Group: 3

Verdict: RUNTIME ERROR

Test 12

Group: 3

Verdict: RUNTIME ERROR

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: RUNTIME ERROR

Test 16

Group: 3

Verdict: ACCEPTED