Submission #1168569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168569		trufanov.p	Alkemija (COCI18_alkemija)	C++20	80 / 80	27 ms	7876 KiB

alkemija

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <queue>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<bool> can_sub(n);
    for (int i = 0; i < m; ++i) {
        int a;
        cin >> a;
        can_sub[a - 1] = true;
    }
    int k;
    cin >> k;
    vector<vector<int>> y(k);
    vector<vector<int>> in_react(n);
    vector<int> need(k);
    queue<int> q;
    for (int i = 0; i < k; ++i) {
        int l, r;
        cin >> l >> r;
        need[i] = l;
        for (int j = 0; j < l; ++j) {
            int x;
            cin >> x;
            x--;
            if (can_sub[x]) {
                need[i]--;
                if (need[i] == 0) {
                    q.push(i);
                }
            } else {
                in_react[x].push_back(i);
            }
        }
        for (int j = 0; j < r; ++j) {
            int y1;
            cin >> y1;
            y1--;
            y[i].push_back(y1);
            //in_react[y1].push_back(i);
        }
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int y1 : y[v]) {
            if (!can_sub[y1]) {
                can_sub[y1] = true;
                for (int r : in_react[y1]) {
                    if (need[r] > 0) {
                        need[r]--;
                        if (need[r] == 0) {
                            q.push(r);
                        }
                    }
                }
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (can_sub[i]) {
            ans.push_back(i + 1);
        }
    }
    cout << ans.size() << '\n';
    for (int i : ans) {
        cout << i << ' ';
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8