oj.uz

Submission #889593

# Submission time Handle Problem Language Result Execution time Memory
889593 2023-12-20T03:36:36 Z zeta7532 Political Development (BOI17_politicaldevelopment) C++17
0 / 100
 3000 ms 29268 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

int main() {
    ll N,K;
    cin >> N >> K;
    vector<set<ll>> s(N);
    set<pair<ll,ll>> S;
    rep(i,N){
        ll D;
        cin >> D;
        rep(j,D){
            ll x;
            cin >> x;
            s[i].insert(x);
        }
        s[i].insert(i);
        S.insert({D+1,i});
    }
    ll ans=0;
    while(S.size()!=0){
        auto it=*S.begin();
        S.erase(it);
        ll sz=it.fi;
        ll i=it.se;
        vector<ll> A(sz);
        auto itr=s[i].begin();
        ll cnt=0;
        while(itr!=s[i].end()){
            A[cnt]=*itr;
            itr++;
            cnt++;
        }
        rep(bit,1<<sz){
            bool ok=true;
            ll l=sz;
            rep(j,sz){
                if(bit&(1<<j)) l--;
                rep(k,sz){
                    if(bit&(1<<j)) continue;
                    if(bit&(1<<k)) continue;
                    if(s[A[j]].find(A[k])==s[A[j]].end()) ok=false;
                }
            }
            if(ok) ans=max(ans,l);
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 46 ms 1628 KB Output is correct
4 Execution timed out 3068 ms 1628 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 46 ms 1628 KB Output is correct
4 Execution timed out 3068 ms 1628 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Execution timed out 3069 ms 29268 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 46 ms 1628 KB Output is correct
4 Execution timed out 3068 ms 1628 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 46 ms 1628 KB Output is correct
4 Execution timed out 3068 ms 1628 KB Time limit exceeded
5 Halted 0 ms 0 KB -