Ryhmät

input/code.cpp: In function 'int main()':
input/code.cpp:112:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                         for (int i = 0; i < path.size() - 1; ++i) {
      |                                         ~~^~~~~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <queue>

using namespace std;

#define a first
#define b second

struct Node {
    int a, b;
    int sink;
    vector<int> sinks;
};

struct Sink {
    int used, max_capacity;
    vector<int> nodes;
};

int main() {
    int node_count, test_count;
    cin >> node_count >> test_count;
    vector<Node> nodes(node_count);
    for (int i = 0; i < node_count; ++i) {
        cin >> nodes[i].a >> nodes[i].b;
    }
    map<int, vector<int>> nodes_start, nodes_ended;
    for (int i = 0; i < node_count; ++i) {
        nodes_start[nodes[i].a].push_back(i);
        nodes_ended[nodes[i].b+1].push_back(i);
    }
    for (int t_ = 0; t_ < test_count; ++t_) {
        for (auto& node : nodes) {
            node.sink = 0;
            node.sinks.clear();
        }

        int sink_count;
        cin >> sink_count;
        set<int> sink_values;
        unordered_map<int, Sink> sinks;
        for (int i = 0; i < sink_count; ++i) {
            int value;
            cin >> value;
            sink_values.insert(value);
            sinks[value].max_capacity += value;
        }
        auto nodes_start_iter = nodes_start.begin();
        auto nodes_ended_iter = nodes_ended.begin();
        unordered_set<int> nodes_active;
        for (int sink: sink_values) {
            while (nodes_start_iter != nodes_start.end() && nodes_start_iter->first <= sink) {
                for (int node_index : nodes_start_iter->second) {
                    nodes_active.insert(node_index);
                }
                ++nodes_start_iter;
            }
            while (nodes_ended_iter != nodes_ended.end() && nodes_ended_iter->first <= sink) {
                for (int node_index : nodes_ended_iter->second) {
                    nodes_active.erase(node_index);
                }
                ++nodes_ended_iter;
            }
            for (int node_index : nodes_active) {
                nodes[node_index].sinks.push_back(sink);
                sinks[sink].nodes.push_back(node_index);
            }
        }
        
        // Ahne aloitus
        for (int sink: sink_values) {
            for (int node_index : sinks[sink].nodes) {
                if (nodes[node_index].sink == 0) {
                    sinks[sink].used += 1;
                    nodes[node_index].sink = sink;
                    if (sinks[sink].used == sinks[sink].max_capacity) {
                        break;
                    }
                }
            }
        }

        // Vaihtoehtoiset reitit
        bool changed = true;
        while (changed) {
            changed = false;
            unordered_set<int> visited;
            queue<vector<int>> bfs;
            for (int i = 0; i < node_count; ++i) {
                if (nodes[i].sink == 0 && !nodes[i].sinks.empty()) {
                    bfs.push({i});
                }
            }
            while (!bfs.empty() && !changed) {
                vector<int> path = bfs.front();
                bfs.pop();
                int last_node_index = path.back();
                if (visited.count(last_node_index)) {
                    continue;
                }
                visited.insert(last_node_index);
                for (int sink : nodes[last_node_index].sinks) {
                    if (sinks[sink].used < sinks[sink].max_capacity) {
                        changed = true;
                        for (int i = 0; i < path.size() - 1; ++i) {
                            nodes[path[i]].sink = nodes[path[i+1]].sink;
                        }
                        nodes[last_node_index].sink = sink;
                        sinks[sink].used += 1;
                        goto end_bfs;
                    }
                }
                for (int sink : nodes[last_node_index].sinks) {
                    if (sinks[sink].used == sinks[sink].max_capacity) {
                        for (int node_index : sinks[sink].nodes) {
                            if (nodes[node_index].sink == sink && !visited.count(node_index)) {
                                //find(path.begin(), path.end(), node_index) == path.end()) {
                                vector<int> new_path = path;
                                new_path.push_back(node_index);
                                bfs.push(new_path);
                            }
                        }
                    }
                }
            }
            end_bfs:;
        }

        bool all_full = true;
        for (int sink: sink_values) {
            if (sinks[sink].used != sinks[sink].max_capacity) {
                all_full = false;
                break;
            }
        }
        if (!all_full) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED