Submission #246588

#	Time	Username	Problem	Language	Result	Execution time	Memory
246588		m3r8	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	256 ms	34552 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];
std::set<int> tst[N];
int k;
std::queue<int> que;
int used[N];
int dg[N];

int clq(std::vector<int> akt, int depth, int idx){
  if(!akt.size() ||depth == k)return depth;
  else{
    int mx = 0;
    for(int i = 0;i<akt.size();i++){
      std::vector<int> nxt;  
      for(int j = i+1;j<akt.size();j++){
        if(tst[akt[i]].count(akt[j])){
          nxt.push_back(akt[j]);  
        };
      };
      mx = std::max(mx,clq(nxt,depth+1,idx));
    };
    return mx;
  };
};

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;
    tst[i].insert(i);
    scanf("%d",&d);
    for(int j = 0;j<d;j++){
      mx = 2;
      scanf("%d",&x);
      tst[i].insert(x);
      adj[i].push_back(x);
    };
  };
  for(int i = 0;i<n;i++){
    dg[i] = adj[i].size();
    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();  
    std::vector<int> akt;
    used[ak] = 2;
    for(auto i: adj[ak]){
      if(used[i] != 2){
        akt.push_back(i);
      };  
    };
    mx = std::max(mx,clq(akt,1,ak));
    for(auto i: adj[ak]){
      if(!used[i]){
        dg[i]--;
        if(dg[i] < k){
          used[i] = 1;
          que.push(i);  
        };
      };  
    };
  };
  printf("%d\n",mx);
  return 0;
};

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int clq(std::vector<int>, int, int)':
politicaldevelopment.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<akt.size();i++){
                   ~^~~~~~~~~~~
politicaldevelopment.cpp:26:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = i+1;j<akt.size();j++){
                       ~^~~~~~~~~~~
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(adj[i].size() < k){
        ~~~~~~~~~~~~~~^~~
politicaldevelopment.cpp:39: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:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&d);
     ~~~~~^~~~~~~~~
politicaldevelopment.cpp:49: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: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23