제출 #1293656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293656		Hamed_Ghaffari	Political Development (BOI17_politicaldevelopment)	C++20	62 / 100	432 ms	17324 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second
#define SZ(x) int(x.size())

const int MXN = 5e4+5;

int n, k, deg[MXN], ans, dp[1<<10], id[MXN], adj[10];
bool mark[MXN];
vector<int> g[MXN];
set<pii> st, edges;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i=0,d; i<n; i++) {
        cin >> d;
        g[i].resize(d);
        for(int &j : g[i]) {
            cin >> j;
            deg[i]++;
            deg[j]++;
            edges.insert({min(i, j), max(i, j)});
        }
    }
    for(int i=0; i<n; i++) st.insert({deg[i], i});
    memset(id, -1, sizeof(id));
    while(!st.empty()) {
        int v = st.begin()->Y;
        st.erase(st.begin());
        mark[v] = 1;
        for(int u : g[v]) if(!mark[u]) {
            st.erase({deg[u], u});
            st.insert({--deg[u], u});
        }
        vector<int> vec = {v};
        for(int u : g[v])
            if(!mark[u])
                vec.push_back(u);
        for(int i=0; i<SZ(vec); i++) id[vec[i]] = i, adj[i] = 0;
        for(int i=0; i<SZ(vec); i++)
            for(int j=i+1; j<SZ(vec); j++)
                if(edges.find({min(vec[i], vec[j]), max(vec[i], vec[j])})!=edges.end())
                    adj[i] |= 1<<j,
                    adj[j] |= 1<<i;
        dp[0] = 1;
        for(int msk=1; msk<(1<<SZ(vec)); msk++) {
            int v = __lg(msk);
            dp[msk] = dp[msk^(1<<v)] & ((msk&(adj[v]|(1<<v)))==msk);
            if(dp[msk]) ans = max(ans, __builtin_popcount(msk));
        }
        for(int i=0; i<SZ(vec); i++) id[vec[i]] = -1;
    }
    cout << ans << '\n';
    return 0;
}

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