oj.uz

Submission #234729

# Submission time Handle Problem Language Result Execution time Memory
234729 2020-05-25T11:30:26 Z ArshiaDadras Ili (COI17_ili) C++14
7 / 100
 7 ms 1536 KB 
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

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

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

bool check(int root) {
	c[root] = '0';
	mark[root] = true;
	for (int u = n + m - 1; u >= n; u--) {
		if (mark[u])
			for (auto v: adj[u])
				if (c[v] == '?') {
					mark[v] = true;
					c[v] = '0';
				}
		bool one = false;
		for (auto v: adj[u])
			one |= c[v] != '0';
		if (c[u] != '?' && c[u] - '0' != one)
			return false;
	}
	return true;
}

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

void solve() {
	assert(m <= 20);
	int And = (1 << m) - 1, Or = 0;
	for (int msk = 0; msk < 1 << n; msk++) {
		bool flag = true;
		for (int u = 0; u < n; u++)
			mark[u] = msk >> u & 1;
		for (int u = n; u < n + m; u++) {
			mark[u] = false;
			for (auto v: adj[u])
				mark[u] |= mark[v];
			flag &= c[u] == '?' || c[u] - '0' == mark[u];
		}
		if (flag) {
			int cur = 0;
			for (int u = n; u < n + m; u++)
				if (mark[u])
					cur |= 1 << u - n;
			And &= cur, Or |= cur;
		}
	}
	for (int u = 0; u < m; u++)
		if ((And >> u & 1) == (Or >> u & 1))
			cout << (Or >> u & 1);
		else
			cout << '?';
	return;
	for (int u = 0; u < n; u++)
		c[u] = '?';
	for (int u = n + m - 1; u >= n; u--)
		if (c[u] == '0')
			for (auto v: adj[u])
				c[v] = '0';
	for (int u = 0; u < n + m; u++) {
		if (c[u] == '?' && !check(u)) {
			mark[u] = false;
			c[u] = '1';
		}
		for (int v = 0; v < n + m; v++)
			if (mark[v]) {
				mark[v] = false;
				c[v] = '?';
			}
	}
	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;
}

Compilation message

ili.cpp: In function 'void solve()':
ili.cpp:67:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
      cur |= 1 << u - n;
                  ~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 7 ms 768 KB Output is correct

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 7 ms 768 KB Output is correct
8 Runtime error 6 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 7 ms 768 KB Output is correct
8 Runtime error 6 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -