Submission #248996

#	Time	Username	Problem	Language	Result	Execution time	Memory
248996		luciocf	Ili (COI17_ili)	C++14	0 / 100	1 ms	512 KiB

ili

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e4+10;

int n, m;
int a[maxn], b[maxn];
int l[maxn], r[maxn];

bool mark[maxn];

void dfs(int u)
{
	mark[u] = 1;
	a[u] = 0;

	if (!mark[l[u]]) dfs(l[u]);
	if (!mark[r[u]]) dfs(r[u]);
}

void do_1(void)
{
	for (int i = n+1; i <= n+m; i++)
	{
		if (a[i] == 0)
		{
			memset(mark, 0, sizeof mark);
			dfs(i);
		}
	}
}

void do_2(void)
{
	while (true)
	{
		bool novo = 0;

		for (int i = n+1; i <= n+m; i++)
			if (a[i] == -1 && a[l[i]] == 0 && a[r[i]] == 0)
				a[i] = 0, novo = 1;

		if (!novo) break;
	}
}

void do_3(void)
{
	for (int i = n+1; i <= n+m; i++)
	{
		if (a[i] != 1) continue;

		if (a[l[i]] == 0) a[r[i]] = 1;
		else if (a[r[i]] == 0) a[l[i]] = 1;
	}
}

bool dfs2(int u)
{
	if (b[u] == 1) return false;

	mark[u] = 1, b[u] = 0;

	if (!mark[l[u]] && !dfs2(l[u])) return false;
	if (!mark[r[u]] && !dfs2(r[u])) return false;

	return true;
}

bool can(int u)
{
	for (int i = n+1; i <= n+m; i++)
	{
		if (a[i] != 1) continue;

		if (l[i] == u && r[i] == 0) return false;
		if (r[i] == u && l[i] == 0) return false;
	}

	memset(mark, 0, sizeof mark);
	memset(b, -1, sizeof b);

	b[u] = 0;
	for (int i = 1; i <= n+m; i++)
		if (a[i] != -1)
			b[i] = a[i];

	if (!dfs2(u)) return false;

	for (int i = n+1; i <= n+m; i++)
		if (b[i] == 1 && !b[l[i]] && !b[r[i]])
			return false;

	return true;
}

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

	memset(a, -1, sizeof a);

	for (int i = 1; i <= m; i++)
	{
		char c;
		scanf(" %c", &c);

		if (c == '1') a[n+i] = 1;
		else if (c == '0') a[n+i] = 0;
	}

	for (int i = 1; i <= m; i++)
	{
		char c1, c2;

		scanf(" %c %c", &c1, &c2);

		if (c1 == 'x') l[n+i] = (int)(c2-'0');
		else l[n+i] = n+(int)(c2-'0');

		scanf(" %c %c", &c1, &c2);

		if (c1 == 'x') r[n+i] = (int)(c2-'0');
		else r[n+i] = n+(int)(c2-'0');
	}

	do_1(); do_2(); do_3();

	for (int i = 1; i <= n+m; i++)
	{
		if (a[i] != -1) continue;

		if (!can(i))
			a[i] = 1;
	}

	for (int i = n+1; i <= n+m; i++)
	{
		if (a[i] == -1) printf("?");
		else if (a[i] == 0) printf("0");
		else printf("1");
	}
	printf("\n");
}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
ili.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~
ili.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %c", &c1, &c2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
ili.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %c", &c1, &c2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 42
• Subtask 3: 0 / 51