제출 #1136364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136364		vasyamer	Alkemija (COCI18_alkemija)	C++20	80 / 80	28 ms	9956 KiB

alkemija

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
 
// #define _GLIBCXX_DEBUG
// #define _GLIBCXX_DEBUG_PEDANTIC
 
#include <iomanip>
#include <cassert>
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <array>
#include <numeric>
#include <queue>
#include <deque>
#include <bitset>
#include <cmath>
#include <climits>
#include <cstdint>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>
 
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

 
const int MOD = 998244353;
const long double PI = 3.141592653589793;
using ll = long long;
const ll INF = 1e18;
 
// #define int ll

// --------> sashko123`s defines:

#define itn int     //Vasya sorry :(
#define p_b push_back
#define fi first
#define se second
#define pii std::pair<int, int>
#define oo LLONG_MAX
#define big INT_MAX
#define elif else if

int input()
{
    int x;
    cin >> x;
    return x;
}

// ----------> end of sashko123`s defines (thank you Vasya <3)

// template<typename K, typename V>
// using hash_table = cc_hash_table<K, V, hash<K>>;

// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

int n, m;
const int N = 2e5;
vector<int> g[N];
int cnt[N];
int used[N];

void solve() {
    cin >> n >> m;
    queue<int> q;
    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        a--;
        if (used[a] == 0) {
            used[a] = 1;
            q.push(a);
        }
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int L, R;
        cin >> L >> R;
        cnt[i + n] = L;
        while (L--) {
            int v;
            cin >> v;
            v--;
            g[v].push_back(i + n);
        }
        while (R--) {
            int v;
            cin >> v;
            v--;
            g[i + n].push_back(v);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (auto to: g[v]) {
            cnt[to]--;
            if (cnt[to] == 0) {
                for (auto j : g[to]) {
                    if (!used[j]) {
                        q.push(j);
                        used[j] = 1;
                    }
                }
            }
        }
    }
    int ans = 0;
    vector<int> b;
    for (int i = 0; i < n; i++) {
        ans += used[i];
        if (used[i])
            b.push_back(i + 1);
    }
    cout << ans << "\n";
    for (auto i : b) {
        cout << i << " ";
    }
}	
 
int32_t main(int32_t argc, const char * argv[]) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    // insert code here...

    int tt= 1;
    // std::cin >> tt;
	for (int t = 1; t <= tt; t++) {
		// cout << "Case #" << t << ": ";
        solve();
    }
    return 0;
}

• 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