Submission #1186949

#TimeUsernameProblemLanguageResultExecution timeMemory
1186949steveonalexFriends (BOI17_friends)C++20
0 / 100
13 ms1096 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1ULL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));} ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ull mask){return __builtin_popcountll(mask);} int ctz(ull mask){return __builtin_ctzll(mask);} int logOf(ull mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); // mt19937_64 rng(1); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } const int N = 2525; int n, p, q; vector<int> graph[N]; vector<vector<int>> usable; void dfs(vector<int> v, set<vector<int>> &S){ if (S.insert(v).second == false) return; vector<int> adj; for(int i: v) for(int j: graph[i]) if (!binary_search(ALL(v), j)) adj.push_back(j); remove_dup(adj); if ((int)adj.size() <= q){ usable.push_back(v); return; } if ((int)v.size() >= p) return; for(int i: adj){ vector<int> _v = v; _v.push_back(i); remove_dup(_v); vector<int> _adj = adj; _adj.erase(lower_bound(ALL(_adj), i)); for(int j: graph[i]) if (!binary_search(ALL(_v), j)) _adj.push_back(j); remove_dup(_adj); if ((int)_v.size() + (int)_adj.size() > p + q) continue; dfs(_v, S); } } void solve(){ cin >> n >> p >> q; for(int i = 0; i < n; ++i){ int m; cin >> m; graph[i].resize(m); for(int &j: graph[i]) cin >> j; sort(ALL(graph[i])); } #define get_detention(){cout << "detention\n"; return;} for(int i = 0; i < n; ++i) if ((int)graph[i].size() >= p + q) get_detention(); for(int i = 0; i < n; ++i) { for(int j: graph[i]){ if (!binary_search(ALL(graph[j]), i)){ get_detention(); } } } set<vector<int>> S; for(int i = 0; i < n; ++i){ vector<int> v = {i}; dfs(v, S); } vector<int> marked(n); vector<vector<int>> ans; for(auto i: usable){ bool check = false; for(int j: i) if (!marked[j]){ marked[j] = 1; check = true; } if (check) { ans.push_back(i); } } if (*min_element(ALL(marked)) == 0) get_detention(); for(int i = 0; i < (int) ans.size(); ++i) for(int j = i+1; j < (int) ans.size(); ++j){ vector<int> sigma; for(int x: ans[j]) if (!binary_search(ALL(ans[i]), x)) sigma.push_back(x); vector<int> adj; for(int x: sigma) for(int y: graph[x]) if (!binary_search(ALL(sigma), y)) adj.push_back(y); if (adj.size() <= q){ ans[j] = sigma; } else{ sigma.clear(); for(int x: ans[i]) if (!binary_search(ALL(ans[j]), x)) sigma.push_back(x); ans[i] = sigma; } } cout << "home\n"; int cnt = 0; for(auto i: ans) cnt += (i.size() > 0); cout << cnt << "\n"; for(auto i: ans){ if (i.size()){ cout << i.size() << " "; printArr(i); } } } int main(void){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); clock_t start = clock(); solve(); cerr << "Time elapsed: " << clock() - start << "ms!\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...