Submission #1035520

#TimeUsernameProblemLanguageResultExecution timeMemory
1035520vjudge1Political Development (BOI17_politicaldevelopment)C++17
39 / 100
3057 ms338260 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma") #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int N = 5e4, X = 5e3; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, k, c, ans; vector<int> vt, adj[N]; set<int> st[N]; bitset<N> bt2[N], r, taken, toTake; void clean(int x) { for (int i = 0; i < n; i++) { if (adj[i].size()+1 < x) r[i] = 1; } } void dfs(int x) { if (c++ > X) return; int sz = taken.count(); if (sz > ans) { ans = sz; clean(sz+1); } shuffle(all(adj[x]), rng); for (int& y : adj[x]) { if (c++ > X) return; if (r[y] || taken[y] || (taken & bt2[y]).count() < sz) continue; taken[y] = 1; bitset<N> toTakePrev = toTake; toTake &= bt2[y]; dfs(y); if (c++ > X) return; toTake = toTakePrev; taken[y] = 0; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; ans = 1; vt.resize(n); for (int i = 0; i < n; i++) { vt[i] = i; bt2[i][i] = toTake[i] = 1; int x; cin >> x; for (int j = 0; j < x; j++) { int y; cin >> y; st[i].insert(y); if (st[y].find(i) != st[y].end()) { bt2[i][y] = 1; adj[i].push_back(y); bt2[y][i] = 1; adj[y].push_back(i); } } } shuffle(all(vt), rng); for (int i = 0; i < n; i++) { if (r[vt[i]]) continue; c = 0; taken.reset(); taken[vt[i]] = 1; toTake = bt2[vt[i]]; dfs(vt[i]); r[vt[i]] = 1; } cout << ans << "\n"; }

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void clean(int)':
politicaldevelopment.cpp:19:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |     if (adj[i].size()+1 < x) r[i] = 1;
      |         ~~~~~~~~~~~~~~~~^~~
politicaldevelopment.cpp: In function 'void dfs(int)':
politicaldevelopment.cpp:35:54: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     if (r[y] || taken[y] || (taken & bt2[y]).count() < sz) continue;
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
#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...