Submission #128730

#	Time	Username	Problem	Language	Result	Execution time	Memory
128730		davitmarg	Political Development (BOI17_politicaldevelopment)	C++17	54 / 100	3040 ms	195072 KiB

politicaldevelopment

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
 
int n,k,used[50004],ans=1;
vector<int> g[50004];
map<pair<int,int>,bool> edge;
vector<pair<int,int>> p;
vector<vector<int>> pol[15];
 
bool check(vector<int> a)
{
	map<int,bool> used;
    for(int i=0;i<a.size();i++)
        for(int j=i+1;j<a.size();j++)
            if(!edge[MP(i,j)] || !edge[MP(j,i)])
				return 0;
 
	return 1;
}
 
int main()
{
        srand(4864);
	cin>>n>>k;
    for(int i=0;i<n;i++)
	{
        int d,to;
        cin>>d;
        while(d--)
		{
            scanf("%d",&to);
            edge[MP(i,to)]=1;
            g[i].PB(to);
            if(i>to)
				p.PB(MP(i,to));
		}
	}
 
    for(int i=0;i<p.size();i++)
	{
        pol[2].PB(vector<int>(0));
        pol[2].back().PB(p[i].first);
        pol[2].back().PB(p[i].second);
        ans=2;
	}
    if(k!=5)
	{
		for(int t=3;t<=k;t++)
		{
			pol[t-2].clear();
			random_shuffle(all(pol[t-1]));
			for(int i=0;i<pol[t-1].size() && i<n;i++)
			{
				random_shuffle(all(pol[t-1][i]));
 
				for(int j=0;j<pol[t-1][i].size();j++)
					used[pol[t-1][i][j]]=1;
				for(int j=0;j<pol[t-1][i].size() && j<n;j++)
				{
					for(int x=0;x<g[pol[t-1][i].back()].size();x++)
					{
						int to=g[pol[t-1][i].back()][x];
						if(used[to])
							continue;
						bool f=1;
						for(int y=0;y<pol[t-1][i].size()-1;y++)
							if(edge.find(MP(pol[t-1][i][y],to))==edge.end())
							{
								f=0;
								break;
							}
						if(f)
						{
							ans=t;
							pol[t].PB(pol[t-1][i]);
							pol[t].back().PB(to);
						}
 
					}
				}
				for(int j=0;j<pol[t-1][i].size();j++)
					used[pol[t-1][i][j]]=0;
			}
		}
	}
	else
	{
		for(int t=3;t<=k;t++)
		{
			pol[t-2].clear();
			random_shuffle(all(pol[t-1]));
			for(int i=0;i<pol[t-1].size() && i<n;i++)
			{
				random_shuffle(all(pol[t-1][i]));
 
				for(int j=0;j<pol[t-1][i].size();j++)
					used[pol[t-1][i][j]]=1;
				for(int j=0;j<pol[t-1][i].size() && j<n/10;j++)
				{
					for(int x=0;x<g[pol[t-1][i].back()].size();x++)
					{
						int to=g[pol[t-1][i].back()][x];
						if(used[to])
							continue;
						bool f=1;
						for(int y=0;y<pol[t-1][i].size()-1;y++)
							if(edge.find(MP(pol[t-1][i][y],to))==edge.end())
							{
								f=0;
								break;
							}
						if(f)
						{
							ans=t;
							pol[t].PB(pol[t-1][i]);
							pol[t].back().PB(to);
						}
 
					}
				}
				for(int j=0;j<pol[t-1][i].size();j++)
					used[pol[t-1][i][j]]=0;
			}
		}
 
	}
    cout<<ans<<endl;
	return 0;
}
 
 
/*
 
 
 
 
*/

Compilation message (stderr)

politicaldevelopment.cpp: In function 'bool check(std::vector<int>)':
politicaldevelopment.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)
                 ~^~~~~~~~~
politicaldevelopment.cpp:35:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i+1;j<a.size();j++)
                       ~^~~~~~~~~
politicaldevelopment.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=0;i<a.size();i++)
     ^~~
politicaldevelopment.cpp:39:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return 1;
  ^~~~~~
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<p.size();i++)
                 ~^~~~~~~~~
politicaldevelopment.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<pol[t-1].size() && i<n;i++)
                ~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<pol[t-1][i].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<pol[t-1][i].size() && j<n;j++)
                 ~^~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int x=0;x<g[pol[t-1][i].back()].size();x++)
                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int y=0;y<pol[t-1][i].size()-1;y++)
                   ~^~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<pol[t-1][i].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:113:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<pol[t-1].size() && i<n;i++)
                ~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:117:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<pol[t-1][i].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:119:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<pol[t-1][i].size() && j<n/10;j++)
                 ~^~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int x=0;x<g[pol[t-1][i].back()].size();x++)
                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int y=0;y<pol[t-1][i].size()-1;y++)
                   ~^~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:142:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<pol[t-1][i].size();j++)
                 ~^~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&to);
             ~~~~~^~~~~~~~~~

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