oj.uz

Submission #1035544

# Submission time Handle Problem Language Result Execution time Memory
1035544 2024-07-26T11:48:16 Z vjudge1 Political Development (BOI17_politicaldevelopment) C++17
16 / 100
 3000 ms 338288 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 = 1e3;

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] && sz+1 <= ans) || 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]);

    if (rng() % 2 == 0) r[vt[i]] = 1;
  }

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

Compilation message

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:71: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     if ((r[y] && sz+1 <= ans) || taken[y] || (taken & bt2[y]).count() < sz) continue;
      |                                              ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 28 ms 26056 KB Output is correct
4 Correct 14 ms 25436 KB Output is correct
5 Correct 20 ms 25516 KB Output is correct
6 Correct 18 ms 25752 KB Output is correct
7 Correct 20 ms 25692 KB Output is correct
8 Correct 21 ms 23928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 15 ms 23996 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 28 ms 26056 KB Output is correct
4 Correct 14 ms 25436 KB Output is correct
5 Correct 20 ms 25516 KB Output is correct
6 Correct 18 ms 25752 KB Output is correct
7 Correct 20 ms 25692 KB Output is correct
8 Correct 21 ms 23928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 15 ms 23996 KB Output is correct
11 Correct 21 ms 25428 KB Output is correct
12 Correct 14 ms 25436 KB Output is correct
13 Correct 4 ms 3932 KB Output is correct
14 Correct 14 ms 25520 KB Output is correct
15 Correct 2 ms 3932 KB Output is correct
16 Correct 16 ms 25692 KB Output is correct
17 Correct 3 ms 3932 KB Output is correct
18 Correct 19 ms 26000 KB Output is correct
19 Correct 19 ms 23900 KB Output is correct
20 Correct 15 ms 25436 KB Output is correct
21 Correct 14 ms 25432 KB Output is correct
22 Correct 14 ms 23900 KB Output is correct
23 Correct 35 ms 26200 KB Output is correct
24 Correct 12 ms 23896 KB Output is correct
25 Correct 28 ms 26460 KB Output is correct
26 Correct 40 ms 26260 KB Output is correct
27 Correct 43 ms 26200 KB Output is correct
28 Correct 43 ms 25944 KB Output is correct
29 Correct 36 ms 26204 KB Output is correct
30 Correct 422 ms 26136 KB Output is correct
31 Correct 50 ms 26456 KB Output is correct
32 Correct 1010 ms 26416 KB Output is correct
33 Correct 43 ms 26460 KB Output is correct
34 Correct 53 ms 26456 KB Output is correct
35 Correct 21 ms 14684 KB Output is correct
36 Correct 21 ms 14684 KB Output is correct
37 Correct 21 ms 14876 KB Output is correct
38 Correct 45 ms 9304 KB Output is correct
39 Correct 48 ms 9304 KB Output is correct
40 Correct 66 ms 27092 KB Output is correct
41 Correct 37 ms 9308 KB Output is correct
42 Correct 47 ms 26972 KB Output is correct
43 Correct 45 ms 26968 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23896 KB Output is correct
2 Correct 2 ms 3928 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 3 ms 3932 KB Output is correct
8 Correct 2 ms 3928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 2 ms 3952 KB Output is correct
11 Correct 2934 ms 335508 KB Output is correct
12 Correct 2 ms 3932 KB Output is correct
13 Correct 2940 ms 337860 KB Output is correct
14 Correct 3 ms 3984 KB Output is correct
15 Correct 2972 ms 337816 KB Output is correct
16 Correct 2863 ms 338000 KB Output is correct
17 Execution timed out 3089 ms 338288 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 28 ms 26056 KB Output is correct
4 Correct 14 ms 25436 KB Output is correct
5 Correct 20 ms 25516 KB Output is correct
6 Correct 18 ms 25752 KB Output is correct
7 Correct 20 ms 25692 KB Output is correct
8 Correct 21 ms 23928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 15 ms 23996 KB Output is correct
11 Correct 21 ms 25428 KB Output is correct
12 Correct 14 ms 25436 KB Output is correct
13 Correct 4 ms 3932 KB Output is correct
14 Correct 14 ms 25520 KB Output is correct
15 Correct 2 ms 3932 KB Output is correct
16 Correct 16 ms 25692 KB Output is correct
17 Correct 3 ms 3932 KB Output is correct
18 Correct 19 ms 26000 KB Output is correct
19 Correct 19 ms 23900 KB Output is correct
20 Correct 15 ms 25436 KB Output is correct
21 Correct 14 ms 25432 KB Output is correct
22 Correct 14 ms 23900 KB Output is correct
23 Correct 35 ms 26200 KB Output is correct
24 Correct 12 ms 23896 KB Output is correct
25 Correct 28 ms 26460 KB Output is correct
26 Correct 40 ms 26260 KB Output is correct
27 Correct 43 ms 26200 KB Output is correct
28 Correct 43 ms 25944 KB Output is correct
29 Correct 36 ms 26204 KB Output is correct
30 Correct 422 ms 26136 KB Output is correct
31 Correct 50 ms 26456 KB Output is correct
32 Correct 1010 ms 26416 KB Output is correct
33 Correct 43 ms 26460 KB Output is correct
34 Correct 53 ms 26456 KB Output is correct
35 Correct 21 ms 14684 KB Output is correct
36 Correct 21 ms 14684 KB Output is correct
37 Correct 21 ms 14876 KB Output is correct
38 Correct 45 ms 9304 KB Output is correct
39 Correct 48 ms 9304 KB Output is correct
40 Correct 66 ms 27092 KB Output is correct
41 Correct 37 ms 9308 KB Output is correct
42 Correct 47 ms 26972 KB Output is correct
43 Correct 45 ms 26968 KB Output is correct
44 Correct 16 ms 28760 KB Output is correct
45 Correct 2 ms 3928 KB Output is correct
46 Correct 53 ms 27156 KB Output is correct
47 Correct 160 ms 28764 KB Output is correct
48 Correct 52 ms 26968 KB Output is correct
49 Correct 176 ms 28800 KB Output is correct
50 Correct 168 ms 28676 KB Output is correct
51 Correct 576 ms 31404 KB Output is correct
52 Correct 13 ms 25948 KB Output is correct
53 Correct 2680 ms 32060 KB Output is correct
54 Incorrect 693 ms 32060 KB Output isn't correct
55 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 28 ms 26056 KB Output is correct
4 Correct 14 ms 25436 KB Output is correct
5 Correct 20 ms 25516 KB Output is correct
6 Correct 18 ms 25752 KB Output is correct
7 Correct 20 ms 25692 KB Output is correct
8 Correct 21 ms 23928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 15 ms 23996 KB Output is correct
11 Correct 21 ms 25428 KB Output is correct
12 Correct 14 ms 25436 KB Output is correct
13 Correct 4 ms 3932 KB Output is correct
14 Correct 14 ms 25520 KB Output is correct
15 Correct 2 ms 3932 KB Output is correct
16 Correct 16 ms 25692 KB Output is correct
17 Correct 3 ms 3932 KB Output is correct
18 Correct 19 ms 26000 KB Output is correct
19 Correct 19 ms 23900 KB Output is correct
20 Correct 15 ms 25436 KB Output is correct
21 Correct 14 ms 25432 KB Output is correct
22 Correct 14 ms 23900 KB Output is correct
23 Correct 35 ms 26200 KB Output is correct
24 Correct 12 ms 23896 KB Output is correct
25 Correct 28 ms 26460 KB Output is correct
26 Correct 40 ms 26260 KB Output is correct
27 Correct 43 ms 26200 KB Output is correct
28 Correct 43 ms 25944 KB Output is correct
29 Correct 36 ms 26204 KB Output is correct
30 Correct 422 ms 26136 KB Output is correct
31 Correct 50 ms 26456 KB Output is correct
32 Correct 1010 ms 26416 KB Output is correct
33 Correct 43 ms 26460 KB Output is correct
34 Correct 53 ms 26456 KB Output is correct
35 Correct 21 ms 14684 KB Output is correct
36 Correct 21 ms 14684 KB Output is correct
37 Correct 21 ms 14876 KB Output is correct
38 Correct 45 ms 9304 KB Output is correct
39 Correct 48 ms 9304 KB Output is correct
40 Correct 66 ms 27092 KB Output is correct
41 Correct 37 ms 9308 KB Output is correct
42 Correct 47 ms 26972 KB Output is correct
43 Correct 45 ms 26968 KB Output is correct
44 Correct 2 ms 3932 KB Output is correct
45 Correct 1541 ms 325660 KB Output is correct
46 Correct 322 ms 308120 KB Output is correct
47 Correct 1272 ms 325972 KB Output is correct
48 Correct 1351 ms 326224 KB Output is correct
49 Correct 146 ms 280864 KB Output is correct
50 Execution timed out 3046 ms 333256 KB Time limit exceeded
51 Halted 0 ms 0 KB -