Submission #248889

#	Time	Username	Problem	Language	Result	Execution time	Memory
248889		Tc14	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	159 ms	24312 KiB

politicaldevelopment

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;

int ans;
ve<int> S, T;
ve<set<int>> G;

void f(int i, int s) {

    bool valid;

    if (i < S.size()) {

        f(i + 1, s);

        valid = true;
        for (int t : T) {
            if (G[t].find(S[i]) == G[t].end()) {
                valid = false;
                break;
            }
        }

        if (valid) {
            T.push_back(S[i]);
            f(i + 1, s + 1);
            T.pop_back();
        }
    }
    else ans = max(ans, s);

}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, d, a, u;
    ve<int> D;
    ve<bool> I;
    queue<int> Q;

    cin >> n >> k;
    G = ve<set<int>>(n);
    D = ve<int>(n);
    I = ve<bool>(n);

    for (int i = 0; i < n; i++) {
        cin >> d;
        D[i] = d;
        for (int j = 0; j < d; j++) {
            cin >> a;
            G[i].insert(a);
        }
        if (d < k) {
            Q.push(i);
            I[i] = true;
        }
    }

    ans = 0;
    for (int i = 0; i < n; i++) {
        u = Q.front();
        Q.pop();
        S.clear();
        for (int v : G[u]) {
            if (D[v] > 0) {
                D[v]--;
                S.push_back(v);
                if (D[v] < k && !I[v]) {
                    Q.push(v);
                    I[v] = true;
                }
            }
        }
        D[u] = 0;
        f(0, 1);
    }

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void f(int, int)':
politicaldevelopment.cpp:15:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < S.size()) {
         ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23