oj.uz

Submission #246256

# Submission time Handle Problem Language Result Execution time Memory
246256 2020-07-08T12:52:40 Z m3r8 Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 3000 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 = 1;
  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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 311032 KB Output is correct
2 Correct 163 ms 310904 KB Output is correct
3 Correct 162 ms 311592 KB Output is correct
4 Correct 162 ms 311544 KB Output is correct
5 Correct 164 ms 311544 KB Output is correct
6 Correct 165 ms 311620 KB Output is correct
7 Correct 158 ms 311592 KB Output is correct
8 Correct 166 ms 310904 KB Output is correct
9 Correct 174 ms 310904 KB Output is correct
10 Correct 157 ms 310976 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 311032 KB Output is correct
2 Correct 163 ms 310904 KB Output is correct
3 Correct 162 ms 311592 KB Output is correct
4 Correct 162 ms 311544 KB Output is correct
5 Correct 164 ms 311544 KB Output is correct
6 Correct 165 ms 311620 KB Output is correct
7 Correct 158 ms 311592 KB Output is correct
8 Correct 166 ms 310904 KB Output is correct
9 Correct 174 ms 310904 KB Output is correct
10 Correct 157 ms 310976 KB Output is correct
11 Correct 155 ms 311544 KB Output is correct
12 Execution timed out 3089 ms 311672 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 311032 KB Output is correct
2 Correct 157 ms 310904 KB Output is correct
3 Correct 157 ms 310904 KB Output is correct
4 Incorrect 157 ms 310976 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 311032 KB Output is correct
2 Correct 163 ms 310904 KB Output is correct
3 Correct 162 ms 311592 KB Output is correct
4 Correct 162 ms 311544 KB Output is correct
5 Correct 164 ms 311544 KB Output is correct
6 Correct 165 ms 311620 KB Output is correct
7 Correct 158 ms 311592 KB Output is correct
8 Correct 166 ms 310904 KB Output is correct
9 Correct 174 ms 310904 KB Output is correct
10 Correct 157 ms 310976 KB Output is correct
11 Correct 155 ms 311544 KB Output is correct
12 Execution timed out 3089 ms 311672 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 311032 KB Output is correct
2 Correct 163 ms 310904 KB Output is correct
3 Correct 162 ms 311592 KB Output is correct
4 Correct 162 ms 311544 KB Output is correct
5 Correct 164 ms 311544 KB Output is correct
6 Correct 165 ms 311620 KB Output is correct
7 Correct 158 ms 311592 KB Output is correct
8 Correct 166 ms 310904 KB Output is correct
9 Correct 174 ms 310904 KB Output is correct
10 Correct 157 ms 310976 KB Output is correct
11 Correct 155 ms 311544 KB Output is correct
12 Execution timed out 3089 ms 311672 KB Time limit exceeded
13 Halted 0 ms 0 KB -