Submission #576139

#	Time	Username	Problem	Language	Result	Execution time	Memory
576139		lumibons	Friends (BOI17_friends)	C++17	100 / 100	284 ms	1492 KiB

friends

#include <bits/stdc++.h>

using namespace std;

int n, p, q;
bool f[3000], m[3000];
vector<int> e[3000];

void mark(vector<int> & g, bool v) {
  for (int i : g)
    m[i] = v;
}

bool anyMarked(vector<int> & g) {
  for (int i : g)
    if (m[i])
      return true;
  return false;
}

bool valid(vector<int> & g) {
  mark(g, true);
  int cq = 0;
  for (int i : g)
    for (int j : e[i])
      cq += !m[j];
  return cq <= q;
}

vector<int> withoutMarked(vector<int> & g) {
  vector<int> h;
  for (int i : g)
    if (!m[i])
      h.push_back(i);
  return h;
}

int main() {
  cin >> n >> p >> q;
  set<pair<int, int>> ed;
  for (int i = 0; i < n; i++) {
    int m, j;
    cin >> m;
    while (m--) {
      cin >> j;
      e[i].push_back(j);
      ed.emplace(i, j);
    }
  }
  for (auto [i, j] : ed)
    if (ed.find({j, i}) == ed.end()) {
      cout << "detention\n";
      return 0;
    }
  vector<vector<int>> par;
  for (int i = 0; i < n; i++) {
    if (f[i])
      continue;
    vector<int> g = {i};
    for (int b = 0; b < (1 << (p + q - 1)) && !f[i];) {
      int gi = 0, gj = 0, cp = 1, cq = 0, k = p + q - 1;
      m[i] = true;
      while (gi < (int) g.size()) {
        if (gj == (int) e[g[gi]].size())
          gi++, gj = 0;
        else if (m[e[g[gi]][gj]])
          gj++;
        else if (k == 0)
          break;
        else {
          bool ig = (b >> --k) & 1;
          if (ig && cp == p || !ig && cq == q)
            break;
          if (ig)
            cp++, m[e[g[gi]][gj]] = true, g.push_back(e[g[gi]][gj]);
          else
            cq++;
          gj++;
        }
      }
      if (gi < (int) g.size()) {
        mark(g, false);
        g.resize(1);
        b &= ~((1 << k) - 1);
        b += 1 << k;
      } else {
        for (int j : g)
          f[j] = true;
        break;
      }
    }
    if (!f[i]) {
      cout << "detention\n";
      return 0;
    }
    for (vector<int> & h : par) {
      if (!anyMarked(h))
        continue;
      vector<int> hw = withoutMarked(h);
      mark(g, false);
      if (valid(hw))
        mark(h, false), h = hw;
      else
        g = withoutMarked(g), mark(h, false);
      mark(g, true);
    }
    mark(g, false);
    par.push_back(g);
  }
  vector<vector<int>> res;
  for (vector<int> & g : par)
    if (!g.empty())
      res.push_back(g);
  cout << "home\n" << res.size() << "\n";
  for (vector<int> & g : res) {
    cout << g.size();
    for (int i : g)
      cout << " " << i;
    cout << "\n";
  }
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:72:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   72 |           if (ig && cp == p || !ig && cq == q)
      |               ~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 37 / 37
• Subtask 3: 12 / 12
• Subtask 4: 31 / 31