oj.uz

Submission #246352

# Submission time Handle Problem Language Result Execution time Memory
246352 2020-07-08T19:36:08 Z kimbj0709 Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 6 ms 2304 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 50050
#define f first
#define s second
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_vertex,k;
  vector<vector<int> > adj(maxn);
  set<pair<int,int> > edges;
  cin >> no_of_vertex >> k;
  int no_of_input,input;
  int ans = 1;
  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q1;
  vector<int> degree(maxn,0);
  for(int i=0;i<no_of_input;i++){
    cin >> no_of_input;
    for(int j=0;j<no_of_input;j++){
      cin >> input;
      adj[i].push_back(input);
      edges.insert({i,input});
    }
    degree[i] = no_of_input;
    q1.push({degree[i],i});
  }
  vector<int> visited(maxn,0);
  while(q1.size()!=0){
    pair<int,int> a = q1.top();
    q1.pop();
    if(visited[a.s]==1){
      continue;
    }
    visited[a.s] = 1;
    vector<int> rn;
    for(auto j:adj[a.s]){
      if(visited[j]==0){
        degree[j]--;
        q1.push({degree[j],j});
        rn.push_back(j);
      }
    }
    int arr[10][10];
    for(int a=0;a<rn.size();a++){
      arr[a][a] = 1;
      for(int b=0;b<rn.size();b++){
        if(a==b){
          continue;
        }
        if(edges.find({rn[a],rn[b]})!=edges.end()){
          arr[a][b] = 1;
        }
        else{
          arr[a][b] = 0;
        }
      }
    }
    for(int j=0;j<(1<<rn.size());j++){
      for(int a=0;a<rn.size();a++){
        if(j&(1<<a)){
          for(int b=0;b<rn.size();b++){
            if(j&(1<<b)){
              if(arr[a][b]==0){
                goto cont;
              }
            }
          }
        }
      }
      ans = max(ans,(int)__builtin_popcount(j));
      cont : ;
    }
  }
  cout << ans+1;
}

Compilation message

politicaldevelopment.cpp: In function 'int32_t main()':
politicaldevelopment.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int a=0;a<rn.size();a++){
                 ~^~~~~~~~~~
politicaldevelopment.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int b=0;b<rn.size();b++){
                   ~^~~~~~~~~~
politicaldevelopment.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int a=0;a<rn.size();a++){
                   ~^~~~~~~~~~
politicaldevelopment.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(int b=0;b<rn.size();b++){
                       ~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct
3 Correct 6 ms 2304 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 5 ms 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Incorrect 6 ms 2304 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct
3 Correct 6 ms 2304 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 5 ms 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Incorrect 6 ms 2304 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct
3 Correct 6 ms 2304 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 5 ms 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Incorrect 6 ms 2304 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct
3 Correct 6 ms 2304 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 5 ms 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Incorrect 6 ms 2304 KB Output isn't correct
9 Halted 0 ms 0 KB -