Submission #934918

#	Time	Username	Problem	Language	Result	Execution time	Memory
934918		irmuun	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	731 ms	336288 KiB

politicaldevelopment

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

ll n,k,d[50000];
vector<vector<bool>>dis(50000,vector<bool>(50000,0));
bool check(vector<ll>&v){
    for(ll i=0;i<v.size();i++){
        for(ll j=i+1;j<v.size();j++){
            if(dis[v[i]][v[j]]==false){
                return false;
            }
        }
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    set<ll>adj[n];
    set<pair<ll,ll>>ord;
    for(ll i=0;i<n;i++){
        cin>>d[i];
        ord.insert({d[i],i});
        for(ll j=0;j<d[i];j++){
            ll u;
            cin>>u;
            adj[i].insert(u);
            dis[i][u]=true;
            dis[u][i]=true;
        }
    }
    ll ans=1;
    while(!ord.empty()){
        auto [s,i]=*ord.begin();
        ord.erase(ord.begin());
        ll sz=adj[i].size();
        ll p=(1ll<<sz);
        vector<ll>v;
        for(ll j=0;j<p;j++){
            ll r=0;
            for(auto x:adj[i]){
                if(j&(1ll<<r)){
                    v.pb(x);
                }
                r++;
            }
            if(check(v)){
                ans=max(ans,(ll)v.size()+1);
            }
            v.clear();
        }
        for(auto x:adj[i]){
            ll y=adj[x].size();
            adj[x].erase(i);
            ord.erase({y,x});
            ord.insert({y-1,x});
        }
        adj[i].clear();
    }
    cout<<ans;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'bool check(std::vector<long long int>&)':
politicaldevelopment.cpp:15:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(ll i=0;i<v.size();i++){
      |                ~^~~~~~~~~
politicaldevelopment.cpp:16:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(ll j=i+1;j<v.size();j++){
      |                      ~^~~~~~~~~

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