Submission #404810

#	Time	Username	Problem	Language	Result	Execution time	Memory
404810		rama_pang	Friends (BOI17_friends)	C++17	100 / 100	337 ms	25228 KiB

friends

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, P, Q;
  cin >> N >> P >> Q;

  const auto Impossible = [&]() {
    cout << "detention\n";
    exit(0);
  };

  vector<vector<int>> adj(N);
  vector<vector<int>> mat(N, vector<int>(N));
  for (int i = 0; i < N; i++) {
    int p;
    cin >> p;
    while (p--) {
      int j;
      cin >> j;
      mat[i][j] = 1;
      adj[i].emplace_back(j);
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (mat[i][j] != mat[j][i]) {
        Impossible();
      }
    }
  }

  // Solution:
  // Consider finding a group for a node u. For every node v
  // not adjacent to u, we don't need to consider them (since
  // it will only increase Q unnecessarily). For every node v
  // adjacent to u, either we pick v (and increase current p)
  // or we don't pick v (and increase current q). This way,
  // we have around 2^{P + Q} total options.
  //
  // We find a group for every node u. This runs in O(N (P + Q) 2^{P + Q}).
  // Then, for every pair of nodes, consider the 2 groups of these
  // nodes. If they arent' disjoint, we want to split them so they
  // are. We can note that:
  //
  // p1, p2 <= P, q1, q2 <= Q
  // Let p3 = intersection of (p1, p2).
  // Then:
  // q1 + edges[p1][p3] <= Q
  // q2 + edges[p3][p2] <= Q.
  // So, min(q1 + edges[p3][p2], q2 + edges[p1][p3]) <= Q.
  //
  // So, we can always split them into disjoint groups. We repair
  // all groups this way in O(N^2 * (P + Q)).
  //
  // Time complexity: O(N * (P + Q) * (N + 2^{P + Q})).

  vector<int> cur;
  vector<int> state;

  const auto GetGroup = [&](const auto &self, int cur_head, int ptr, int p, int q, vector<int> &res) {
    if (!res.empty()) return;
    if (p > P || q > Q) return;
    if (cur_head == p) { // found group
      res = cur;
      return;
    }

    int u = cur[cur_head];
    if (adj[u].size() == ptr) {
      return self(self, cur_head + 1, 0, p, q, res);
    }

    int v = adj[u][ptr];
    if (state[v] == 0) { // v is undecided
      state[v] = -1;
      self(self, cur_head, ptr + 1, p, q + 1, res);
      state[v] = +1;
      cur.emplace_back(v);
      self(self, cur_head, ptr + 1, p + 1, q, res);
      cur.pop_back();
      state[v] = 0;
    } else if (state[v] == -1) { // we already decided not to pick this node
      return self(self, cur_head, ptr + 1, p, q + 1, res);
    } else if (state[v] == +1) { // we already picked this node in group
      return self(self, cur_head, ptr + 1, p, q, res);
    }
  };

  vector<vector<int>> inGroup(N);
  for (int u = 0; u < N; u++) {
    state.assign(N, 0);
    cur = {u};
    state[u] = 1;
    GetGroup(GetGroup, 0, 0, 1, 0, inGroup[u]);
    if (inGroup[u].empty()) {
      Impossible();
    }
  }

  const auto IsValid = [&](const vector<int> &A) {
    if (A.size() > P) return false;
    int q = 0;
    static vector<int> in(N);
    for (auto i : A) in[i] = 1;
    for (auto i : A) for (auto j : adj[i]) if (!in[j]) q++;
    for (auto i : A) in[i] = 0;
    return q <= Q;
  };

  const auto FixGroup = [&](int x, int y) {
    static vector<int> who(N);
    for (auto i : inGroup[x]) who[i] = 0;
    for (auto i : inGroup[y]) who[i] = 0;
    for (auto i : inGroup[x]) who[i] |= 1;
    for (auto i : inGroup[y]) who[i] |= 2;

    bool intersect = false;
    for (auto i : inGroup[x]) if (who[i] == 3) intersect = true;
    for (auto i : inGroup[y]) if (who[i] == 3) intersect = true;

    if (!intersect) return true;

    static vector<int> xA, yA; xA.clear(); yA.clear();
    static vector<int> xB, yB; xB.clear(); yB.clear();

    for (auto i : inGroup[x]) {
      if (who[i] == 1) {
        xA.emplace_back(i);
        xB.emplace_back(i);
      } else {
        xA.emplace_back(i);
      }
    }

    for (auto i : inGroup[y]) {
      if (who[i] == 2) {
        yA.emplace_back(i);
        yB.emplace_back(i);
      } else {
        yA.emplace_back(i);
      }
    }

    if (IsValid(xA) && IsValid(yB)) {
      inGroup[x] = xA;
      inGroup[y] = yB;
    } else if (IsValid(xB) && IsValid(yA)) {
      inGroup[x] = xB;
      inGroup[y] = yA;
    } else {
      return false;
    }
    return true;
  };

  state.assign(N, 0);
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      assert(FixGroup(i, j));
    }
  }

  vector<vector<int>> answer;
  for (int i = 0; i < N; i++) {
    if (!inGroup[i].empty()) {
      answer.emplace_back(inGroup[i]);
    }
  }

  cout << "home\n";
  cout << answer.size() << '\n';
  for (auto &a : answer) {
    sort(begin(a), end(a));
    cout << a.size();
    for (auto i : a) cout << ' ' << i;
    cout << '\n';
  }
  return 0;
}

Compilation message (stderr)

friends.cpp: In instantiation of 'main()::<lambda(const auto:23&, int, int, int, int, std::vector<int>&)> [with auto:23 = main()::<lambda(const auto:23&, int, int, int, int, std::vector<int>&)>]':
friends.cpp:99:46:   required from here
friends.cpp:74:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     if (adj[u].size() == ptr) {
      |         ~~~~~~~~~~~~~~^~~~~~
friends.cpp: In lambda function:
friends.cpp:106:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     if (A.size() > P) return false;
      |         ~~~~~~~~~^~~

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