제출 #1284728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284728		enzy	Political Development (BOI17_politicaldevelopment)	C++20	77 / 100	3092 ms	8468 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
const int maxk=11;
int marc[maxn], deg[maxn], m[maxk][maxk], id[maxn], dp[(1<<maxk)];
vector<int>v[maxn];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, k; cin >> n >> k;
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++){
        cin >> deg[i];
        for(int j=1;j<=deg[i];j++){
            int x; cin >> x;
            v[i].push_back(++x);
        }
        s.insert({deg[i],i});
    }
    memset(id,-1,sizeof(id));
    int resp=1;
    while(!s.empty()){
        auto f=s.begin();
        int u=f->second;
        marc[u]++;
        s.erase(f);
        vector<int>caras; caras.push_back(u);
        for(int x : v[u]){
            if(!marc[x]){
                s.erase({deg[x],x});
                deg[x]--;
                s.insert({deg[x],x});
                caras.push_back(x);
            }
        }
        int tam=caras.size();
        for(int i=0;i<tam;i++) id[caras[i]]=i;
        for(int i=0;i<tam;i++)
            for(int x : v[caras[i]]) if(id[x]!=-1) m[id[caras[i]]][id[x]]=1;
        for(int i=0;i<tam;i++)
            for(int j=0;j<tam;j++) 
                if(m[i][j]) dp[(1<<i)+(1<<j)]=1;
        for(int i=0;i<(1<<tam);i++){
            int qtd=0;
            for(int k=0;k<tam;k++) if(i&(1<<k)) qtd++; 
            if(dp[i]) resp=max(resp,qtd);
            if(qtd<=2) continue;
            bool ok=true;
            for(int k=0;k<tam;k++){
                if(i&(1<<k)){
                    if(!dp[i^(1<<k)]) ok=false;
                }
            }
            if(ok){
                dp[i]=1;
                resp=max(resp,qtd);
            }
        }
        for(int i=0;i<tam;i++) id[caras[i]]=-1;
        for(int i=0;i<(1<<tam);i++) dp[i]=0;
        for(int i=0;i<tam;i++)
            for(int j=0;j<tam;j++) m[i][j]=0;
    }
    cout << resp << endl;
}

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