oj.uz

Submission #1035431

# Submission time Handle Problem Language Result Execution time Memory
1035431 2024-07-26T11:01:57 Z vjudge1 Political Development (BOI17_politicaldevelopment) C++17
4 / 100
 391 ms 43916 KB 
#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 = 5e5, */X2 = 5e0;

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++ > X2) return;

  int sz = taken.count();
  ans = max(ans, sz);
  
  shuffle(all(adj[x]), rng);
  for (int& y : adj[x]) { 
    if (c++ > X2) return;
    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 (c++ > X) return;
    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]);
  }
  */

  shuffle(all(vt), rng);
  for (int i = 0; i < n; i++) {
    c = 0;

    taken.reset();
    taken[vt[i]] = 1;
    toTake = bt2[vt[i]];

    dfs2(vt[i]);
  }

  cout << ans << "\n";
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 39 ms 43916 KB Output is correct
4 Correct 354 ms 42780 KB Output is correct
5 Correct 370 ms 42840 KB Output is correct
6 Correct 45 ms 43100 KB Output is correct
7 Correct 44 ms 43096 KB Output is correct
8 Correct 13 ms 21592 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 13 ms 21596 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 39 ms 43916 KB Output is correct
4 Correct 354 ms 42780 KB Output is correct
5 Correct 370 ms 42840 KB Output is correct
6 Correct 45 ms 43100 KB Output is correct
7 Correct 44 ms 43096 KB Output is correct
8 Correct 13 ms 21592 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 13 ms 21596 KB Output is correct
11 Correct 355 ms 42980 KB Output is correct
12 Correct 391 ms 42916 KB Output is correct
13 Correct 1 ms 1624 KB Output is correct
14 Correct 368 ms 42588 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 44 ms 43076 KB Output is correct
17 Incorrect 1 ms 1628 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21596 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 2 ms 1760 KB Output is correct
5 Incorrect 1 ms 1628 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 39 ms 43916 KB Output is correct
4 Correct 354 ms 42780 KB Output is correct
5 Correct 370 ms 42840 KB Output is correct
6 Correct 45 ms 43100 KB Output is correct
7 Correct 44 ms 43096 KB Output is correct
8 Correct 13 ms 21592 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 13 ms 21596 KB Output is correct
11 Correct 355 ms 42980 KB Output is correct
12 Correct 391 ms 42916 KB Output is correct
13 Correct 1 ms 1624 KB Output is correct
14 Correct 368 ms 42588 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 44 ms 43076 KB Output is correct
17 Incorrect 1 ms 1628 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 39 ms 43916 KB Output is correct
4 Correct 354 ms 42780 KB Output is correct
5 Correct 370 ms 42840 KB Output is correct
6 Correct 45 ms 43100 KB Output is correct
7 Correct 44 ms 43096 KB Output is correct
8 Correct 13 ms 21592 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 13 ms 21596 KB Output is correct
11 Correct 355 ms 42980 KB Output is correct
12 Correct 391 ms 42916 KB Output is correct
13 Correct 1 ms 1624 KB Output is correct
14 Correct 368 ms 42588 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 44 ms 43076 KB Output is correct
17 Incorrect 1 ms 1628 KB Output isn't correct
18 Halted 0 ms 0 KB -