Submission #745425

#	Time	Username	Problem	Language	Result	Execution time	Memory
745425		MilosMilutinovic	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	2580 ms	35620 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int n, k, id[N], f[N];
set<int> g[N];
vector<int> rg[N];
bool was[N];
int main() {
    scanf("%d%d", &n, &k);
    set<pair<int, int>> st;
    for (int i = 0; i < n; i++) {
        int d;
        scanf("%d", &d);
        for (int j = 0; j < d; j++) {
            int x;
            scanf("%d", &x);
            g[i].insert(x);
            rg[x].push_back(i);
        }
        st.emplace(d, i);
    }
    for (int i = 0; i < n; i++) id[i] = -1;
    int ans = 0;
    while (!st.empty()) {
        auto it = st.begin();
        int v = it->second;
        st.erase(it);
        vector<int> ver(1, v);
        for (int x : g[v]) ver.push_back(x);
        int deg = (int) ver.size();
        for (int i = 0; i < deg; i++) id[ver[i]] = i;
        for (int x : ver) {
            f[x] = (1 << id[x]);
            for (int y : ver) if (g[x].find(y) != g[x].end()) f[x] += (1 << id[y]);
        }
        for (int mask = 0; mask < (1 << deg); mask++) {
            bool ok = true;
            for (int i = 0; i < deg; i++) if (mask >> i & 1) {
                if ((f[ver[i]] & mask) != mask) ok = false;
            }
            if (ok) ans = max(ans, __builtin_popcount(mask));
        }
        for (int x : rg[v]) g[x].erase(v);
        for (int x : ver) id[x] = -1, f[x] = 0;
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d", &d);
      |         ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:16:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

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