Submission #246585

#	Time	Username	Problem	Language	Result	Execution time	Memory
246585		m3r8	Political Development (BOI17_politicaldevelopment)	C++14	39 / 100	3108 ms	313848 KiB

politicaldevelopment

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <bitset>
#include <utility>
#include <queue>

#define N 50100
#define ii std::pair<int,int>


std::vector<int> adj[N];
int k;
std::vector<std::bitset<N>> add(N);
std::queue<int> que;
std::vector<int> akt;
int used[N];


int clq(int idx){
  int erg = 0;
  for(int i = 0;i<(1<<akt.size());i++){
    std::bitset<N> tmp = add[idx];
    int cnt = 1;
    for(int j = 0;j<akt.size();j++){
      if(i & (1<<j)){
        cnt++;
        tmp &= add[akt[j]];
      };  
    };
    int pos = 1;
    for(int j = 0;j<akt.size();j++){
      if(i & (1<<j) && !tmp[akt[j]]){
        pos = 0;
        break;
      };  
    };
    if(pos){
      erg = std::max(erg,cnt);
    };
  };
  return erg;
};

int main(void){
  int n;  
  scanf("%d %d",&n,&k);
  int d;
  int x;
  int mx = 0;
  for(int i = 0;i<n;i++){
    mx = 1;
    add[i][i] = 1;
    scanf("%d",&d);
    for(int j = 0;j<d;j++){
      mx = 2;
      scanf("%d",&x);
      add[i][x] = 1;
      adj[i].push_back(x);
    };
  };
  for(int i = 0;i<n;i++){
    if(adj[i].size() < k){
      //printf("%d %d\n",i,adj[i].size());
      used[i] = 1;
      que.push(i);
    };  
  };
  while(que.size()){
    int ak = que.front();que.pop();  
    akt.clear();
    used[ak] = 2;
    for(auto i: adj[ak]){
      if(used[i] != 2){
        akt.push_back(i);
      };  
    };
    mx = std::max(mx,clq(ak));
    for(auto i: adj[ak]){
      if(!used[i]){
        add[i][ak] = 0;
        if(add[i].count() <= k){
          used[i] = 1;
          que.push(i);  
        };
      };  
    };
  };
  printf("%d\n",mx);
  return 0;
};

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int clq(int)':
politicaldevelopment.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j<akt.size();j++){
                   ~^~~~~~~~~~~
politicaldevelopment.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j<akt.size();j++){
                   ~^~~~~~~~~~~
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(adj[i].size() < k){
        ~~~~~~~~~~~~~~^~~
politicaldevelopment.cpp:83:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(add[i].count() <= k){
            ~~~~~~~~~~~~~~~^~~~
politicaldevelopment.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&k);
   ~~~~~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&d);
     ~~~~~^~~~~~~~~
politicaldevelopment.cpp:58:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&x);
       ~~~~~^~~~~~~~~

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