Submission #286917

#	Time	Username	Problem	Language	Result	Execution time	Memory
286917		AlexLuchianov	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	594 ms	27100 KiB

politicaldevelopment

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 50000;
std::set<int> g[1 + nmax];
int used[1 + nmax];
std::queue<int> q;

int solve(int node) {
  int sz = g[node].size();
  std::vector<int> neighbours;
  for(std::set<int>::iterator it = g[node].begin(); it != g[node].end(); it++)
    neighbours.push_back(*it);
  std::vector<int> dp(1 << sz, 1);
  dp[0] = 1;
  for(int i = 0; i < sz; i++)
    for(int j = i + 1; j < sz; j++)
      if(g[neighbours[i]].find(neighbours[j]) == g[neighbours[i]].end())
        dp[(1 << i) | (1 << j)] = 0;
  int result = 0;
  for(int mask = 1; mask < (1 << sz); mask++) {
    for(int j = 0; j < sz; j++)
      if(0 < ((1 << j) & mask))
        dp[mask] &= dp[mask ^ (1 << j)]; 
    if(dp[mask] == 1)
      result = std::max(result, __builtin_popcount(mask));
  }
  return result + 1;
}

int main() {
  int n, k;
  std::cin >> n >> k;
  for(int i = 0; i < n; i++) {
    int d;
    std::cin >> d;
    for(int j = 0; j < d; j++) {
      int val;
      std::cin >> val;
      g[i].insert(val);
    }
  }
  
  for(int i = 0; i < n; i++) {
    if(g[i].size() < k) {
      used[i] = 1;
      q.push(i);
    }
  }
  int result = 1;
  while(0 < q.size()) {
    int node = q.front();
    q.pop();
    result = std::max(result, solve(node));
    std::set<int>::iterator it = g[node].begin();
    while(it != g[node].end()) {
      int to = *it;
      g[to].erase(node);
      if(g[to].size() < k && used[to] == 0) {
        used[to] = 1;
        q.push(to);
      }
      it++;
    }
  }
  std::cout << result;
  return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:54:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     if(g[i].size() < k) {
      |        ~~~~~~~~~~~~^~~
politicaldevelopment.cpp:68:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |       if(g[to].size() < k && used[to] == 0) {
      |          ~~~~~~~~~~~~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23