Submission #249142

#TimeUsernameProblemLanguageResultExecution timeMemory
249142blacktulipNorela (info1cup18_norela)C++17
0 / 100
2 ms384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long lo; typedef pair< lo,lo > PII; #define fi first #define se second #define int long long #define mp make_pair #define endl "\n" #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) #define ort ((bas+son)/2) const lo inf = 1000000000000000000; const lo KOK = 100000; const lo LOG = 30; const lo li = 65; const lo mod = 1000000007; int n,m,b[li],a[li][li],k,flag,t,no[li],l[li],comp; int cev; string s; map<int,vector<int>> vec; map<int,int> mpp; vector<int> mini; inline void f(int sira,int mask){ if(sira>=m/2){ for(int i=1;i<=n;i++)no[i]=0; for(int i=0;i<m;i++){ if((mask&(1ll<<i))==0)continue; for(int j=1;j<=l[i];j++){ no[a[i][j]]++; } } flag=0; FOR{ if(no[i]%2==0)flag=1; } vector<int> v; //~ if(flag==1)return ; for(int i=0;i<m;i++){ if((mask&(1ll<<i))==0)continue; v.pb(i+1); } if(flag==0){ if((int)mini.size()==0)swap(mini,v); else if((int)mini.size()>(int)v.size())swap(mini,v); else if((int)mini.size()==(int)v.size() && v<mini)swap(mini,v); return ; } int maski=0; FOR{ if(no[i]%2)maski=(maski|(1ll<<i)); } //~ cout<<"**"<<maski<<"**\n"; if((int)vec[maski].size()==0)swap(vec[maski],v); else if((int)vec[maski].size()>(int)v.size())swap(vec[maski],v); else if((int)vec[maski].size()==(int)v.size() && v<vec[maski])swap(vec[maski],v); return ; } f(sira+1,mask); f(sira+1,(mask|(1ll<<sira))); } inline void f1(int sira,int mask){ if(sira>=m){ for(int i=1;i<=n;i++)no[i]=0; for(int i=0;i<m;i++){ if((mask&(1ll<<i))==0)continue; for(int j=1;j<=l[i];j++){ no[a[i][j]]++; } } flag=0; FOR{ if(no[i]%2==0)flag=1; } vector<int> v; //~ if(flag==1)return ; for(int i=0;i<m;i++){ if((mask&(1ll<<i))==0)continue; v.pb(i+1); } if(flag==0){ if((int)mini.size()==0)swap(mini,v); else if((int)mini.size()>(int)v.size())swap(mini,v); else if((int)mini.size()==(int)v.size() && v<mini)swap(mini,v); return ; } int maski=0; FOR{ if(no[i]%2)maski=(maski|(1ll<<i)); } int maski1=(comp^maski); //~ cout<<"()"<<maski1<<"()"<<endl; if((int)vec[maski1].size()==0)return ; vector<int> vv; for(int i=0;i<(int)vec[maski1].size();i++)vv.pb(vec[maski1][i]); for(int i=0;i<(int)v.size();i++)vv.pb(v[i]); if((int)mini.size()==0)swap(mini,vv); else if((int)mini.size()>(int)vv.size())swap(mini,vv); else if((int)mini.size()==(int)vv.size() && vv<mini)swap(mini,vv); return ; } f1(sira+1,mask); f1(sira+1,(mask|(1ll<<sira))); } main(void){ scanf("%lld %lld",&n,&m); for(int i=0;i<=n;i++){ comp+=(1ll<<i); } for(int i=0;i<m;i++){ scanf("%lld",&l[i]); for(int j=1;j<=l[i];j++)scanf("%lld",&a[i][j]); } f(0,0); f1(m/2,0); printf("%lld\n",(int)mini.size()); for(int i=0;i<(int)mini.size();i++){ printf("%lld ",mini[i]); } return 0; }

Compilation message (stderr)

norela.cpp:118:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
norela.cpp: In function 'int main()':
norela.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
norela.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&l[i]);
   ~~~~~^~~~~~~~~~~~~~
norela.cpp:125:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int j=1;j<=l[i];j++)scanf("%lld",&a[i][j]);
                           ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...