Submission #1102087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102087		crafticat	Viruses (BOI20_viruses)	C++17	0 / 100	1 ms	336 KiB

Viruses

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
template<typename T>
using V = vector<T>;
using vi = V<ll>;
using vvi = V<vi>;
using pi = pair<ll,ll>;
using vpi = V<pi>;

#define F0R(i, n) for(ll i = 0; i < n;i++)
#define FOR(i,a, n) for(ll i = a; i < n;i++)
#define pb push_back

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int g, n, m; cin >> g >> n >> m;
    V<vvi> table(g + 1);

    F0R(i, n) {
        int a, k; cin >> a >> k;
        vi gen;
        F0R(j, k) {
            int x; cin >> x;
            gen.push_back(x);
        }
        table[a].pb(gen);
    }

    vi dp(g,-1);
    while (true) {
        int minal = 1e9;
        int id = 0;

        FOR(i, 2, g) {
            for (auto v : table[i]) {
                bool pos = true;
                int sum = 0;
                for (auto x : v) {
                    if (x > 2 && dp[x] == -1) pos = false;
                    else {
                        if (x <= 2) sum++;
                        else sum += dp[x];
                    }
                }
                if (pos && sum < minal && dp[i] == -1) {
                    minal = sum;
                    id = i;
                }
            }
        }
        if (minal == 1e9) break;
        dp[id] = minal;
    }

    FOR(i, 2, g) {
        if (dp[i] == -1)
            cout << "YES\n";
        else
            cout << "NO " << dp[i] << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18