oj.uz

Submission #223815

# Submission time Handle Problem Language Result Execution time Memory
223815 2020-04-16T13:58:28 Z jk_ Political Development (BOI17_politicaldevelopment) C++14
23 / 100
 250 ms 524292 KB 
#include <bits/stdc++.h>  // score: 100
using namespace std;

int clique_n;
array<bitset<10>, 10> adjmat;
vector<uint8_t> selected;
int largest_clique(int i) {
  if (i == clique_n)
    return selected.size();
  int best = largest_clique(i+1);  // skip i

  bool can_take_i = true;
  for (auto j : selected) {
    if (!adjmat[i][j]) {
      can_take_i = false;
      break;
    }
  }
  if (can_take_i) {
    selected.push_back(i);
    best = max(best, largest_clique(i)); // take i
    selected.pop_back();
  }
  return best;
}

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n, m; cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> degree(n);
  for (int i = 0; i < n; ++i) {
    cin >> degree[i];
    for (int j = 0; j < degree[i]; ++j) {
      int b; cin >> b;
      g[i].push_back(b);
    }
  }
  vector<bool> removed(n);
  priority_queue<pair<size_t, int>> pq;
  for (int i = 0; i < n; ++i)
    pq.emplace(degree[i], i);
  for (auto& v : g)
    sort(v.begin(), v.end());
  
  auto has_edge = [&](int a, int b) {
		    return binary_search(g[a].begin(), g[a].end(), b);
		  };
  int best = 1;
  
  while (!pq.empty()) {
    auto [_, i] = pq.top();
    pq.pop();
    if (removed[i])
      continue;
    vector<int> nbs = g[i];
    nbs.erase(remove_if(nbs.begin(), nbs.end(), [&](int v){ return removed[v]; }),
	      nbs.end());
    
    adjmat = {};
    selected.clear();
    clique_n = nbs.size();
    for (size_t i = 0; i < nbs.size(); ++i) {
      for (size_t j = 0; j < nbs.size(); ++j) {
	if (i != j)
	  adjmat[i][j] = has_edge(nbs[i], nbs[j]);
      }
    }
    best = max(best, 1+largest_clique(0));   // 1+ because we always take i itself
    removed[i] = true;
    for (auto i : nbs) {
      --degree[i];
      pq.emplace(degree[i], i);
    }
  }
  cout << best << '\n';
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:54:10: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto [_, i] = pq.top();
          ^
politicaldevelopment.cpp:54:15: warning: unused variable '_' [-Wunused-variable]
     auto [_, i] = pq.top();
               ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Runtime error 250 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Runtime error 250 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 180 ms 12516 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 180 ms 12496 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 181 ms 12520 KB Output is correct
16 Correct 188 ms 12520 KB Output is correct
17 Correct 179 ms 12524 KB Output is correct
18 Correct 190 ms 12628 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Runtime error 250 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Runtime error 250 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -