Submission #234758

#	Time	Username	Problem	Language	Result	Execution time	Memory
234758		ArshiaDadras	Ili (COI17_ili)	C++14	49 / 100	10 ms	1920 KiB

ili

/* In the name of Allah */
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;

const int N = 2e4 + 5;
vector<int> adj[N];
char c[N], C[N];
bool mark[N];
int n, m;

int read() {
	getchar();
	char x; int u;
	cin >> x >> u;
	if (x ^ 'x')
		u += n;
	return --u;
}

bool go() {
	while (true) {
		bool flag = false;
		for (int u = n + m - 1; u >= n; u--) {
			bool ok = true;
			for (auto v: adj[u])
				ok &= c[v] == '0';
			if (ok) {
				if (c[u] == '1')
					return false;
				if (c[u] == '?')
					c[u] = '0', flag = true;
			}
			if (c[u] == '0')
				for (auto v: adj[u])
					if (c[v] != '0')
						c[v] = '0', flag = true;
		}
		for (int u = n; u < n + m; u++) {
			bool ok = false;
			for (auto v: adj[u])
				ok |= c[v] == '1';
			if (ok) {
				if (c[u] == '0')
					return false;
				if (c[u] == '?')
					c[u] = '1', flag = true;
			}
		}
		if (!flag)
			break;
	}
	return true;
}

bool check(int u) {
	return c[u] = '0', go();
}

void read_input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> c[n + i];
	for (int i = 0; i < m; i++) {
		adj[n + i].push_back(read());
		adj[n + i].push_back(read());
	}
}

void solve() {
	for (int u = 0; u < n; u++)
		c[u] = '?';
	assert(go());
	for (int u = 0; u < n + m; u++)
		if (c[u] == '?') {
			copy(c, c + n + m, C);
			if (!check(u))
				C[u] = '1';
			copy(C, C + n + m, c);
			if (c[u] != '?')
				assert(go());
		}
	for (int i = 0; i < m; i++)
		cout << c[n + i];
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}

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