oj.uz

Submission #246255

# Submission time Handle Problem Language Result Execution time Memory
246255 2020-07-08T12:51:50 Z m3r8 Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 175 ms 311672 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <bitset>
#include <utility>

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


std::set<int> tst[N];
std::vector<int> adj[N];
int k;
std::vector<std::bitset<N>> add(N);

int cclq(std::bitset<N> akt, std::bitset<N> can, int idx, int depth){
  int mx = depth;

  if(akt.count() < depth)return depth-1;
  else if(depth >= k)return depth;
  else{
    for(int i = 0;i<adj[idx].size();i++){
      if((add[adj[idx][i]]&can).count() >= depth){
        can[adj[idx][i]] = 1;
        mx = std::max(mx,cclq(akt&add[adj[idx][i]],can,adj[idx][i],depth+1));
        can[adj[idx][i]] = 0;
      };
    };
  };
  return mx;
};

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;
  };
};
std::vector<ii> edg;
int main(void){
  int n;  
  scanf("%d %d",&n,&k);

  int d;
  int x;
  for(int i = 0;i<n;i++){
    add[i][i] = 1;
    scanf("%d",&d);
    for(int j = 0;j<d;j++){
      scanf("%d",&x);
      add[i][x] = 1;
      if(x > i){
        edg.push_back({i,x});
        adj[i].push_back(x);
      };
      tst[i].insert(x);
    };
  };
  int mx = 0;
  if(k > 5){
    for(int i = 0;i<n;i++){
      int tmp = clq(adj[i],1,i);
      //printf("%d %d %d\n",i,tmp,adj[i].size());
      mx = std::max(tmp,mx);
      if(mx == k)break;
    };
  }else{
    std::bitset<N> can;
    for(auto i: edg){
      mx = 2;
      can[i.first] = 1;
      can[i.second] = 1;
      int tmp = cclq(add[i.first]&add[i.second],can,i.second,2);
      can[i.first] = 0;
      can[i.second] = 0;
      mx = std::max(tmp,mx);
      if(mx == k)break;
    };  
  };
  printf("%d\n",mx);
  return 0;
};

Compilation message

politicaldevelopment.cpp: In function 'int cclq(std::bitset<50100>, std::bitset<50100>, int, int)':
politicaldevelopment.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(akt.count() < depth)return depth-1;
      ~~~~~~~~~~~~^~~~~~~
politicaldevelopment.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<adj[idx].size();i++){
                   ~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:24:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if((add[adj[idx][i]]&can).count() >= depth){
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
politicaldevelopment.cpp: In function 'int clq(std::vector<int>, int, int)':
politicaldevelopment.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<akt.size();i++){
                   ~^~~~~~~~~~~
politicaldevelopment.cpp:40: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:53: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:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&d);
     ~~~~~^~~~~~~~~
politicaldevelopment.cpp:61:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&x);
       ~~~~~^~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 311056 KB Output is correct
2 Correct 153 ms 310904 KB Output is correct
3 Correct 159 ms 311648 KB Output is correct
4 Correct 158 ms 311544 KB Output is correct
5 Correct 160 ms 311672 KB Output is correct
6 Correct 158 ms 311544 KB Output is correct
7 Correct 162 ms 311544 KB Output is correct
8 Incorrect 157 ms 310904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 311056 KB Output is correct
2 Correct 153 ms 310904 KB Output is correct
3 Correct 159 ms 311648 KB Output is correct
4 Correct 158 ms 311544 KB Output is correct
5 Correct 160 ms 311672 KB Output is correct
6 Correct 158 ms 311544 KB Output is correct
7 Correct 162 ms 311544 KB Output is correct
8 Incorrect 157 ms 310904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 311032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 311056 KB Output is correct
2 Correct 153 ms 310904 KB Output is correct
3 Correct 159 ms 311648 KB Output is correct
4 Correct 158 ms 311544 KB Output is correct
5 Correct 160 ms 311672 KB Output is correct
6 Correct 158 ms 311544 KB Output is correct
7 Correct 162 ms 311544 KB Output is correct
8 Incorrect 157 ms 310904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 311056 KB Output is correct
2 Correct 153 ms 310904 KB Output is correct
3 Correct 159 ms 311648 KB Output is correct
4 Correct 158 ms 311544 KB Output is correct
5 Correct 160 ms 311672 KB Output is correct
6 Correct 158 ms 311544 KB Output is correct
7 Correct 162 ms 311544 KB Output is correct
8 Incorrect 157 ms 310904 KB Output isn't correct
9 Halted 0 ms 0 KB -