제출 #248881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248881		Tc14	Political Development (BOI17_politicaldevelopment)	C++17	39 / 100	164 ms	27760 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;
    queue<int> Q;

    cin >> n >> k;
    G = ve<set<int>>(n);
    D = ve<int>(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);
    }

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

    cout << ans << endl;

    return 0;
}

컴파일 시 표준 에러 (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: 0 / 38
• Subtask 5: 0 / 23