Submission #246355

#	Time	Username	Problem	Language	Result	Execution time	Memory
246355		kimbj0709	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	722 ms	44600 KiB

politicaldevelopment

#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_vertex;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 = {a.s};
    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=1;j<(1<<rn.size());j+=2){
      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;
}

Compilation message (stderr)

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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23