oj.uz

Submission #1064357

# Submission time Handle Problem Language Result Execution time Memory
1064357 2024-08-18T11:51:15 Z turska Political Development (BOI17_politicaldevelopment) C++17
23 / 100
 3000 ms 76660 KB 
#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();

}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 39 ms 8252 KB Output is correct
5 Correct 12 ms 8284 KB Output is correct
6 Execution timed out 3075 ms 24300 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 39 ms 8252 KB Output is correct
5 Correct 12 ms 8284 KB Output is correct
6 Execution timed out 3075 ms 24300 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7772 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2816 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 391 ms 76492 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 384 ms 76628 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 392 ms 76584 KB Output is correct
16 Correct 394 ms 76540 KB Output is correct
17 Correct 424 ms 76440 KB Output is correct
18 Correct 403 ms 76660 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 39 ms 8252 KB Output is correct
5 Correct 12 ms 8284 KB Output is correct
6 Execution timed out 3075 ms 24300 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 39 ms 8252 KB Output is correct
5 Correct 12 ms 8284 KB Output is correct
6 Execution timed out 3075 ms 24300 KB Time limit exceeded
7 Halted 0 ms 0 KB -