Submission #1064357

#TimeUsernameProblemLanguageResultExecution timeMemory
1064357turskaPolitical Development (BOI17_politicaldevelopment)C++17
23 / 100
3075 ms76660 KiB
#include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; // const ll M = 998244353; const ll M = 1e9 + 7; #define all(v) (v).begin(), (v).end() #define ff first #define ss second const ll INFL = 1e18; const int INF = 1e9; const int maxN = 50000; bool dp[maxN][1<<10]; set<int> adj[maxN]; void solve() { int n, k; cin >> n >> k; for (int i=0; i<n; i++) { int d; cin >> d; for (int j=0; j<d; j++) { int x; cin >> x; adj[i].insert(x); } } int ans = 1; for (int i=0; i<n; i++) { vector<int> cur; for (auto v: adj[i]) cur.push_back(v); dp[i][0] = true; for (int msk=1; msk<1<<cur.size(); msk++) { int p = __lg(msk); bool ok = dp[i][msk^(1<<p)]; for (int j=0; j<p; j++) { if (!(msk&(1<<j))) continue; ok &= adj[cur[j]].count(cur[p]); } dp[i][msk] = ok; if (ok) { ans = max(ans, __builtin_popcount(msk)+1); } } for (auto v: cur) adj[v].erase(i); } cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); // cout << setprecision(12); int tc = 1; // cin >> tc; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...