oj.uz

Submission #286914

# Submission time Handle Problem Language Result Execution time Memory
286914 2020-08-31T07:06:45 Z AlexLuchianov Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 13 ms 3200 KB 
#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[i].find(j) == g[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 = 0;
  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;
}

Compilation message

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 10 ms 3200 KB Output is correct
4 Correct 11 ms 3200 KB Output is correct
5 Correct 13 ms 3200 KB Output is correct
6 Correct 10 ms 3200 KB Output is correct
7 Correct 10 ms 3200 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 10 ms 3200 KB Output is correct
4 Correct 11 ms 3200 KB Output is correct
5 Correct 13 ms 3200 KB Output is correct
6 Correct 10 ms 3200 KB Output is correct
7 Correct 10 ms 3200 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 10 ms 3200 KB Output is correct
12 Correct 12 ms 3200 KB Output is correct
13 Incorrect 3 ms 2688 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2724 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Incorrect 2 ms 2688 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 10 ms 3200 KB Output is correct
4 Correct 11 ms 3200 KB Output is correct
5 Correct 13 ms 3200 KB Output is correct
6 Correct 10 ms 3200 KB Output is correct
7 Correct 10 ms 3200 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 10 ms 3200 KB Output is correct
12 Correct 12 ms 3200 KB Output is correct
13 Incorrect 3 ms 2688 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 10 ms 3200 KB Output is correct
4 Correct 11 ms 3200 KB Output is correct
5 Correct 13 ms 3200 KB Output is correct
6 Correct 10 ms 3200 KB Output is correct
7 Correct 10 ms 3200 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 10 ms 3200 KB Output is correct
12 Correct 12 ms 3200 KB Output is correct
13 Incorrect 3 ms 2688 KB Output isn't correct
14 Halted 0 ms 0 KB -