Submission #1035424

#TimeUsernameProblemLanguageResultExecution timeMemory
1035424vjudge1Political Development (BOI17_politicaldevelopment)C++17
0 / 100
3065 ms7292 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 = 5e3, X = 5e2, X2 = 5e1; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, k, c, ans; vector<int> vt, adj[N]; bitset<N> bt[N], bt2[N], taken, toTake; void dfs2(int x) { if (c++ > X) return; int sz = taken.count(); ans = max(ans, sz); shuffle(all(adj[x]), rng); for (int& y : adj[x]) { if (!taken[y] && (taken & bt2[y]).count() < sz) continue; taken[y] = 1; bitset<N> toTakePrev = toTake; toTake &= bt2[y]; dfs2(y); if (c > X2) return; toTake = toTakePrev; taken[y] = 0; } } void dfs(int x) { if (c++ > X) return; int sz = taken.count(); ans = max(ans, sz); shuffle(all(adj[x]), rng); for (int& y : adj[x]) { if (!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; c = 0; 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; bt[i][y] = 1; if (bt[y][i]) { 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 && c < X; i++) { dfs(vt[i]); } for (int i = 0; i < n; i++) { c = 0; taken.reset(); toTake.reset(); toTake = ~toTake; dfs2(vt[i]); } cout << ans << "\n"; }

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void dfs2(int)':
politicaldevelopment.cpp:24:47: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     if (!taken[y] && (taken & bt2[y]).count() < sz) continue;
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
politicaldevelopment.cpp: In function 'void dfs(int)':
politicaldevelopment.cpp:46:47: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |     if (!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...