Submission #129149

#	Time	Username	Problem	Language	Result	Execution time	Memory
129149		davitmarg	Political Development (BOI17_politicaldevelopment)	C++17	Compilation error	0 ms	0 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],c[(1<<11)+5],ind[50004],s[50004],f[(1<<11)+5],ans=1;
vector<int> g[50004];
queue<int> q;

int main()
{
	cin>>n>>k;
    for(int i=0;i<n;i++)
	{
        int d,x;
        cin>>d;
        for(int j=0;j<d;j++)
		{
			scanf("%d",&x);
			g[i].PB(x);
		}
		s[i]=g[i].size();
	}

    for(int i=1;i<(1<<k);i++)
		for(int j=0;j<k;j++)
			if(((1<<j)&i))
			{
				c[i]++;
				f[i]=j;
			}

    for(int i=0;i<n;i++)
        if(s[i]<k)
            q.push(i);

    while(!q.empty())
	{
        int v=q.front();
        q.pop();
        if(used[v])
			continue;
		used[v]=1;
        vector<int> a,mask;
        for(int i=0;i<g[v].size();i++)
		{
			int to=g[v][i];
			if(!used[to])
				a.PB(to);
			s[to]--;
            if(s[to]<k)
				q.push(to);
		}
		mask.resize(a.size(),0);
		for(int i=0;i<a.size();i++)
            ind[a[i]]=i;
		for(int i=0;i<a.size();i++)
		{
			for(int j=0;j<g[a[i]].size();j++)
			{
				int to=g[a[i]][j];
				if(used[to])
					continue;
				mask[i]+=(1<<ind[to]);
			}
		}
        vector<bool> dp((1<<a.size())+10);
        dp[0]=1;
        for(int m=1;m<(1<<a.size());m++)
		{
            int bit=f[m];
            int y=mask-(1<<bit)
            if( (mask[bit]&y)==y && dp[y])
			{
				dp[m]=1;
				ans=max(ans,c[m]+1);
			}
		}

	}
	cout<<ans<<endl;
	return 0;
}


/*

4 2
2 1 4
2 0 2
2
2 4 0

*/

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[v].size();i++)
                     ~^~~~~~~~~~~~
politicaldevelopment.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<a.size();i++)
               ~^~~~~~~~~
politicaldevelopment.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<a.size();i++)
               ~^~~~~~~~~
politicaldevelopment.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<g[a[i]].size();j++)
                ~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:91:23: error: no match for 'operator-' (operand types are 'std::vector<int>' and 'int')
             int y=mask-(1<<bit)
                   ~~~~^~~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from politicaldevelopment.cpp:2:
/usr/include/c++/7/bits/stl_iterator.h:389:5: note: candidate: template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
     operator-(const reverse_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:389:5: note:   template argument deduction/substitution failed:
politicaldevelopment.cpp:91:31: note:   'std::vector<int>' is not derived from 'const std::reverse_iterator<_Iterator>'
             int y=mask-(1<<bit)
                               ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from politicaldevelopment.cpp:2:
/usr/include/c++/7/bits/stl_iterator.h:1191:5: note: candidate: template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
     operator-(const move_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1191:5: note:   template argument deduction/substitution failed:
politicaldevelopment.cpp:91:31: note:   'std::vector<int>' is not derived from 'const std::move_iterator<_IteratorL>'
             int y=mask-(1<<bit)
                               ^
In file included from /usr/include/c++/7/vector:65:0,
                 from politicaldevelopment.cpp:5:
/usr/include/c++/7/bits/stl_bvector.h:208:3: note: candidate: std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
   ^~~~~~~~
/usr/include/c++/7/bits/stl_bvector.h:208:3: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::_Bit_iterator_base&'
In file included from /usr/include/c++/7/deque:64:0,
                 from /usr/include/c++/7/queue:60,
                 from politicaldevelopment.cpp:10:
/usr/include/c++/7/bits/stl_deque.h:351:5: note: candidate: template<class _Tp, class _Ref, class _Ptr> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _Ref, _Ptr>&)
     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_deque.h:351:5: note:   template argument deduction/substitution failed:
politicaldevelopment.cpp:91:31: note:   'std::vector<int>' is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
             int y=mask-(1<<bit)
                               ^
In file included from /usr/include/c++/7/deque:64:0,
                 from /usr/include/c++/7/queue:60,
                 from politicaldevelopment.cpp:10:
/usr/include/c++/7/bits/stl_deque.h:363:5: note: candidate: template<class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _RefR, _PtrR>&)
     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_deque.h:363:5: note:   template argument deduction/substitution failed:
politicaldevelopment.cpp:91:31: note:   'std::vector<int>' is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
             int y=mask-(1<<bit)
                               ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from politicaldevelopment.cpp:2:
/usr/include/c++/7/bits/stl_iterator.h:962:5: note: candidate: template<class _Iterator, class _Container> typename __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:962:5: note:   template argument deduction/substitution failed:
politicaldevelopment.cpp:91:31: note:   'std::vector<int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
             int y=mask-(1<<bit)
                               ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from politicaldevelopment.cpp:2:
/usr/include/c++/7/bits/stl_iterator.h:950:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> decltype ((__lhs.base() - __rhs.base())) __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:950:5: note:   template argument deduction/substitution failed:
politicaldevelopment.cpp:91:31: note:   'std::vector<int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
             int y=mask-(1<<bit)
                               ^
politicaldevelopment.cpp:91:17: warning: unused variable 'y' [-Wunused-variable]
             int y=mask-(1<<bit)
                 ^
politicaldevelopment.cpp:38:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~