Submission #1284732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284732		enzy	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	1099 ms	96608 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
const int maxk=11;
int marc[maxn], deg[maxn], id[maxn], dp[(1<<maxk)];
map<pair<int,int>,int>m;
vector<int>v[maxn];
int main(){
    //ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, k; scanf("%d%d", &n, &k);
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++){
        scanf("%d", &deg[i]);
        for(int j=1;j<=deg[i];j++){
            int x; scanf("%d", &x);
            v[i].push_back(++x);
            m[{i,x}]=1;
        }
        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();
        assert(tam<=k+1);
        for(int i=0;i<tam;i++)
            for(int j=0;j<tam;j++) 
                if(m[{caras[i],caras[j]}]==1) 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;
    }
    printf("%d\n", resp);
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:10:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     int n, k; 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", &deg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |             int x; scanf("%d", &x);
      |                    ~~~~~^~~~~~~~~~

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