Submission #1128512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128512		JelalTkm	Political Development (BOI17_politicaldevelopment)	C++20	77 / 100	3089 ms	32140 KiB

politicaldevelopment

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
using namespace std;
 
#define int long long int
 
const int N = 5e3 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;
 
struct Compare {
  bool operator()(const pair<vector<int>, int>& a, const pair<vector<int>, int>& b) const {
    return a.first.size() > b.first.size();
  }
};
 
int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n, k;
    cin >> n >> k;
    vector<multiset<int>> a(n, multiset<int> ());
    vector<vector<int>> b(n, vector<int> ());
    // vector<vector<int>> mp(N, vector<int> (N));
    for (int i = 0; i < n; i++) {
      int d;
      cin >> d;
      while (d--) {
        int x;
        cin >> x;
        // mp[i][x] = 1;
        a[i].insert(x);
        b[i].push_back(x);
      }
    }
 
    set<pair<vector<int>, int>, Compare> q;
    int ans = 0;
    vector<int> e;
    for (int w = 0; w < n; w++) {
      if (w >= 0) {
        map<int, bool> vs;
        q.insert(make_pair(e, w));
        while (!q.empty()) {
          auto [v, u] = *q.begin();
          ans = max(ans, (int) v.size() + 1);
          // cout << u << '\n';
          // for (auto r : v)
          //   cout << r << " ";
          // cout << '\n';
          q.erase(q.begin());
          for (auto i : b[u]) {
            auto v1 = v;
            bool ok = 1;
            for (auto j : v) {
              if (a[i].find(j) == a[i].end()) {
                ok = 0;
                break;
              }
            }
            if (ok && !vs[i]) {
              v1.push_back(u);
              q.insert(make_pair(v1, i));
            }
          }
          vs[u] = 1;
        }
      }
    }
 
    cout << ans << '\n';
  }
 
  return 0;
}

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