Submission #1307940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307940		StefanSebez	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	656 ms	72440 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=5e4+50;
vector<int>E[N];
int n,K,deg[N];
bool was[N];
map<ll,bool>mapa;
int main(){
    scanf("%i%i",&n,&K);
    for(int i=0;i<n;i++){
        int m;scanf("%i",&m);
        for(int j=1;j<=m;j++){
            int u;scanf("%i",&u);
            E[i].pb(u);
            deg[i]++;
            mapa[u+(((ll)i)<<32)]=true;
        }
    }
    int res=0;
    queue<int>kju;
    for(int i=0;i<n;i++)if(deg[i]<K)kju.push(i);
    while(!kju.empty()){
        int u=kju.front();kju.pop();
        if(was[u])continue;
        was[u]=true;
        vector<int>temp;
        for(auto i:E[u])if(!was[i])temp.pb(i);
        E[u]=temp;
        int m=E[u].size();
        for(int mask=0;mask<1<<m;mask++){
            bool moze=true;
            for(int i=0;i<m&&moze;i++)if(mask>>i&1){
                for(int j=i+1;j<m&&moze;j++)if(mask>>j&1){
                    if(!mapa[E[u][i]+(((ll)E[u][j])<<32)])moze=false;
                }
            }
            if(moze)res=max(res,1+__builtin_popcount(mask));
        }
        for(auto i:E[u]){
            deg[i]--;
            if(deg[i]<K)kju.push(i);
        }
    }
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%i%i",&n,&K);
      |     ~~~~~^~~~~~~~~~~~~~
politicaldevelopment.cpp:17:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         int m;scanf("%i",&m);
      |               ~~~~~^~~~~~~~~
politicaldevelopment.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |             int u;scanf("%i",&u);
      |                   ~~~~~^~~~~~~~~

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