Submission #721148

#	Time	Username	Problem	Language	Result	Execution time	Memory
721148		ktkerem	Political Development (BOI17_politicaldevelopment)	C++17	0 / 100	4 ms	5076 KiB

politicaldevelopment

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef int ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;  
const ll limit = 1e9+7;
const ll sus = 5e4+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll n , k;
std::vector<ll> adj[sus] , v[sus];
std::map<ll , ll> mp[sus];
std::set<llll> st;
ll dlt[sus] , dd[sus] , ist[4080];
void solve(){
  std::cin >> n >> k;
  for(ll i = 0 ; n>i;i++){
    ll d;std::cin >> d;
    dd[i] = d;
    for(ll j = 0;d>j;j++){
      ll x;std::cin >> x;
      adj[i].pb(x);
      v[x].pb(i);
      mp[i][x] = 1;
    }
    st.insert({dd[i] , i});
  }
  ll ans = 1;
  while(!st.empty()){
    llll a = *st.begin();
    st.erase(st.begin());
    std::vector<ll> vv;
    dlt[a.sec] = 1;
    for(auto j:adj[a.sec]){
      if(dlt[j] == 0){
        vv.pb(j);
      }
    }
    ll o = vv.size();
    memset(ist , 0 , sizeof(ist));
    ist[0] = 1;
    for(auto j:v[a.sec]){
      if(dlt[j] == 1){
        continue;
      }
      st.erase(st.find({dd[j] , j}));
      dd[j]--;
      st.insert({dd[j] , j});
    }
    if(o > 12){
      while(1){
        debug;
      }
    }
    for(ll i = 1;(1ll << o) > i;i++){
      ll ff = (1ll << std::__lg(i)) ^ i;
      //std::cout << i << " " << ff << " " << vv[std::__lg(i)] << " " << a.sec << "\n";
      if(ist[ff] == 0 || mp[vv[std::__lg(i)]][a.sec] == 0){
        continue;
      }
      ll kd = 1;
      for(ll j = 0;o>j;j++){
        if(((ff & (1ll << j)) && (mp[vv[j]][vv[std::__lg(i)]] == 0)) && (vv[std::__lg(i)] != j)){
          kd = 0;
          break;
        }
      }
      //std::cout << i << " " << kd << " " << ff << "\n";
      ist[i] = kd;
      if(kd){
        ans = std::max(ans , __builtin_popcount(i) + 1);
      }
    }
  }
  std::cout << ans << "\n";
  return;/**/
}
int main(){
  std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
  #ifndef ONLINE_JUDGE
    freopen("in.txt" , "r" , stdin);
    freopen("out.txt" , "w" , stdout);
  #endif
  ll t = 1;
  //std::cin >> t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

politicaldevelopment.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen("in.txt" , "r" , stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen("out.txt" , "w" , stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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