Submission #310669

#	Time	Username	Problem	Language	Result	Execution time	Memory
310669		MrDomino	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	303 ms	9208 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

const int N=50000+7;
const int T=10;
int n;
int k;
vector<int> g[N];
bool active[N];
int deg[N];
set<pair<int,int>> _set_;
int sol;
int id[N];
int bits[1<<T];
int mask[1<<T];
int some_bit[1<<T];

bool is_edge(int x,int y)
{
        if (active[x]==0||active[y]==0)
                return 0;
        if ((int)g[x].size()>(int)g[y].size())
                swap(x,y);
        int l=0,r=(int)g[x].size()-1;
        while (l<=r)
        {
                int m=(l+r)/2;
                if (g[x][m]==y)
                        return 1;
                if (g[x][m]<y)
                        l=m+1;
                else
                        r=m-1;
        }
        return 0;
}

int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);

        for (int i=1;i<(1<<T);i++)
        {
                bits[i]=bits[i/2]+i%2;
                if (i&1)
                        some_bit[i]=1;
                else
                        some_bit[i]=2*some_bit[i/2];
        }
        /** read the input **/
        cin>>n>>k;
        for (int i=0;i<n;i++)
        {
                int len;
                cin>>len;
                g[i].resize(len);
                for (int j=0;j<len;j++)
                        cin>>g[i][j];
                sort(g[i].begin(),g[i].end());
                deg[i]=len;
                active[i]=1;
                _set_.insert({len,i});
        }

        for (int i=0;i<n;i++)
                id[i]=-1;

        /** maximum clique algorithm **/
        while (!_set_.empty())
        {
                int node=_set_.begin()->second;
                _set_.erase({deg[node],node});
                if (active[node]==0)
                        continue;
                for (auto &j:g[node])
                {
                        if (active[j])
                        {
                                _set_.erase({deg[j],j});
                                deg[j]--;
                                _set_.insert({deg[j],j});
                        }
                }
                active[node]=0;
                vector<int> real_g;
                for (auto &x : g[node])
                        if (active[x])
                                real_g.push_back(x);
                int t=(int) real_g.size();
                mask[0]=(1<<t);
                for (int i=1;i<(1<<t);i++)
                        mask[i]=0;
                for (int i=0;i<t;i++)
                        mask[1<<i]+=1<<i;
                for (int i=0;i<(int)real_g.size();i++)
                        for (int j=0;j<i;j++)
                                if (is_edge(real_g[i],real_g[j]))
                                        mask[1<<i]+=1<<j,
                                        mask[1<<j]+=1<<i;
                for (int i=1;i<(1<<t);i++)
                {
                        if (mask[i]==0)
                        {
                                int j=some_bit[i];
                                mask[i]=mask[j]&mask[i^j];
                        }
                        if ((mask[i]&i)==i)
                                sol=max(sol,bits[i]);
                }
        }
        sol++;
        cout<<sol<<"\n";
}
/**

war plan :
(.) get the node with minimum degree using a priority_queue
(.)
(.)
(.)
(.)
(.)
(.)
(.)
(.)
(.)
**/

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