Submission #851173

#	Time	Username	Problem	Language	Result	Execution time	Memory
851173		kderylo	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	659 ms	38224 KiB

politicaldevelopment

#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int stala=5e4+10;
const int st=(1<<12);
vector<int>w[stala];
vector<int>odw_w[stala];
int deg[stala];
set<pair<int,int> >s;
set<pair<int,int> >krawedzie;
vector<int>pom;
int tab[st];
int number_of_bits(int ile,int dl)
{
    int wyn=0;
    for(int i=0;i<dl;i++){
        if((ile&(1<<i))>0){
            wyn++;
        }
    }
    return wyn;
}
int find_subset()
{
    int dl=(int)pom.size();
    int wyn=0;
    for(int i=0;i<dl;i++){
        tab[(1<<i)]=1;
        for(int j=i+1;j<dl;j++){
            int x=((1<<i)|(1<<j));
            if(krawedzie.find({pom[i],pom[j]})!=krawedzie.end()&&krawedzie.find({pom[j],pom[i]})!=krawedzie.end()){
                tab[x]=1;
            }
        }
    }
    for(int i=1;i<(1<<dl);i++){
        if(tab[i]!=1&&number_of_bits(i,dl)>2){
            tab[i]=1;
            for(int j=0;j<dl;j++){
                if((i&(1<<j))>0){
                    tab[i]&=(tab[i-(1<<j)]);
                }
            }
        }
        if(tab[i]==1){
            wyn=max(wyn,number_of_bits(i,dl));
        }
    }
    for(int i=0;i<(1<<dl);i++){
        tab[i]=0;
    }
    return wyn;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,k;
    cin>>ile>>k;
    for(int i=0;i<ile;i++){
        int il;
        cin>>il;
        for(int j=0;j<il;j++){
            int a;
            cin>>a;
            deg[i]++;
            w[i].push_back(a);
            odw_w[a].push_back(i);
            krawedzie.insert({i,a});
        }
    }
    int wyn=0;
    for(int i=0;i<ile;i++){
        s.insert({deg[i],i});
    }
    for(int i=0;i<ile;i++){
        int x=s.begin()->second;
        deg[x]=-1;
        s.erase(s.begin());
        for(int j=0;j<(int)odw_w[x].size();j++){
            if(deg[odw_w[x][j]]!=-1){
            	int wie=odw_w[x][j];
            	int de=deg[wie];
            	deg[wie]--;
            	s.erase({de,wie});
            	de--;
            	s.insert({de,wie});
            }
        }
        pom.clear();
        pom.push_back(x);
        for(int j=0;j<(int)w[x].size();j++){
            if(deg[w[x][j]]!=-1){
                pom.push_back(w[x][j]);
            }
        }
        wyn=max(wyn,find_subset());
    }
    cout<<wyn;
 
    return 0;
}

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