Submission #211244

#	Time	Username	Problem	Language	Result	Execution time	Memory
211244		Lawliet	Amusement Park (CEOI19_amusementpark)	C++17	19 / 100	3076 ms	512 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 20;

int n, m;

int ingrau[MAXN];

vector< int > adj[MAXN];

vector< pii > edges;

bool hasCycle()
{
	queue< int > q;

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

	int cnt = 0;

	while( !q.empty() )
	{
		int cur = q.front();
		q.pop();

		cnt++;

		for(int i = 0 ; i < adj[cur].size() ; i++)
		{
			int viz = adj[cur][i];

			if( --ingrau[viz] == 0 )
				q.push( viz );
		}
	}

	return ( cnt != n );
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int i = 1 ; i <= m ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		edges.push_back( { U , V } );
	}

	lli ans = 0;

	for(int mask = 0 ; mask < (1 << m) ; mask++)
	{
		for(int i = 1 ; i <= n ; i++)
		{
			ingrau[i] = 0;
			adj[i].clear();
		}

		for(int i = 0 ; i < m ; i++)
		{
			int U = edges[i].first;
			int V = edges[i].second;

			if( mask & (1 << i) ) swap( U , V );
			
			ingrau[V]++;
			adj[U].push_back( V );
		}

		if( !hasCycle() ) ans += __builtin_popcount( mask );
	}

	printf("%lld\n",ans);
}

Compilation message (stderr)

amusementpark.cpp: In function 'bool hasCycle()':
amusementpark.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[cur].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~
amusementpark.cpp: In function 'int main()':
amusementpark.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
amusementpark.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37