Submission #91355

#	Time	Username	Problem	Language	Result	Execution time	Memory
91355		YottaByte	Marriage questions (IZhO14_marriage)	C++14	14 / 100	1586 ms	4732 KiB

marriage

#include <stdio.h>
#include <iostream>
using namespace std;

#define pb push_back
#define ll long long
#define fr first
#define sc second
#define mk make_pair

const int N = 1000;
const int M = 500;

int n, m, k, ans, d[N + 1][N + 1];
int tr, tb[N + 1][M + 1];

string t(int a, int b)
{
	string res = "";
	while(a)
	{
		res += char((a % b) + '0');
		a /= b;
	}
	
	while(res.size() < m)
		res += '0';
	
	return res;
}

void check(int l, int cur, int p)
{
	if(d[l][cur])
	{
		//puts("BEEN HERE\n");
		return;
	}
	
	if(p == tr)
	{
		d[l][cur] = 1;
		ans += (n - cur + 1);
		//puts("GOTCHA");
		//cout << cur << " " << t(p, 2) << endl << endl;
		return;
	}
	
	if(cur == n)
	{
		//found = true;
		//puts("TRY\n");
		return;
	}
	
	int cho = 0;
	for(int i = 0; i < m; i++)
	{
		if(tb[i][cur])
		{
			cho |= (1 << i);
		}
	}
	
	//cout << l << " " << cur + 1 << " " << t(cho, 2) << " " << t(p, 2) << endl;
	
	for(int i = 0; i < m; i++)
	{
		if((cho >> i) & 1)
		{
			check(l, cur + 1, (cho & (1 << i)) | p);
		}
	}
}

main()
{
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < k; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		
		a--, b--;
		tb[b][a] = 1;
	}
	
	//for(int j = 0; j < n * 2; j++)
		//cout << '-';
	//puts("");
	//for(int i = 0; i < m; i++)
	//{
		//for(int j = 0; j < n; j++)
		//{
			//if(tb[i][j]) cout << "+";
			//else cout << " ";
			//cout << "|";
		//}
		//puts("");
		
		//for(int j = 0; j < n * 2; j++)
			//cout << '-';
		//puts("");
	//}
	
	if(n < m)
	{
		puts("0");
		return 0;
	}
	
	tr = (1 << m) - 1;
	for(int l = 0; l < n; l++)
	{
		//puts("START");
		check(l, l, 0);
	}
	
	printf("%d", ans);
}
/**

5 3 7
1 1
1 2
1 3
2 3
3 2
4 2
5 1

**/

Compilation message (stderr)

marriage.cpp: In function 'std::__cxx11::string t(int, int)':
marriage.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(res.size() < m)
        ~~~~~~~~~~~^~~
marriage.cpp: At global scope:
marriage.cpp:76:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
marriage.cpp: In function 'int main()':
marriage.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 100