Submission #890576

#	Time	Username	Problem	Language	Result	Execution time	Memory
890576		zeta7532	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1979 ms	102332 KiB

politicaldevelopment

#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<ll> deg(N,0);
    vector<vector<ll>> G(N);
    vector<map<ll,ll>> M(N);
    rep(i,N){
        cin >> deg[i];
        rep(j,deg[i]){
            ll x;
            cin >> x;
            G[i].push_back(x);
            M[i][x]++;
        }
        M[i][i]++;
    }
    vector<bool> seen(N,false);
    set<pair<ll,ll>> s;
    rep(i,N) s.insert({deg[i],i});
    ll ans=0;
    while(s.size()>0){
        auto it=*s.begin();
        s.erase(it);
        ll i=it.se;
        vector<ll> A;
        rep(j,G[i].size()){
            if(seen[G[i][j]]) continue;
            A.push_back(G[i][j]);
        }
        ll sz=A.size();
        rep(bit,1<<sz){
            vector<ll> B;
            rep(j,sz) if(bit&(1<<j)) B.push_back(A[j]);
            bool ok=true;
            ll sz_B=B.size();
            rep(j,sz_B) rep(k,sz_B) if(M[B[j]][B[k]]==0) ok=false;
            if(ok) ans=max(ans,sz_B);
        }
        seen[i]=true;
        for(ll j:G[i]){
            if(seen[j]) continue;
            s.erase({deg[j],j});
            deg[j]--;
            s.insert({deg[j],j});
        }
    }
    cout << ans+1 << endl;
    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:10:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define rep(i,n) for(ll i=0;i<n;i++)
......
   39 |         rep(j,G[i].size()){
      |             ~~~~~~~~~~~~~     
politicaldevelopment.cpp:39:9: note: in expansion of macro 'rep'
   39 |         rep(j,G[i].size()){
      |         ^~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23