oj.uz

Submission #234769

# Submission time Handle Problem Language Result Execution time Memory
234769 2020-05-25T13:58:37 Z ArshiaDadras Ili (COI17_ili) C++14
0 / 100
 5 ms 896 KB 
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;
vector<int> adj[N][2];
bitset<N> B[N], Z;
bool mark[N];
int n, m;
string c;

int read() {
	string s;
	cin >> s;
	int u = stoi(s.substr(1));
	if (s[0] ^ 'x')
		u += n;
	return --u;
}

void read_input() {
	cin >> n >> m >> c;
	for (int i = 0; i < m; i++)
		for (auto u: {read(), read()})
			if (u < n) {
				B[i].set(u);
				adj[i][0].push_back(u);
			}
			else {
				B[i] |= B[u -= n];
				adj[i][1].push_back(u);
			}
}

void solve() {
	for (int u = 0; u < m; u++)
		if (c[u] == '0')
			Z |= B[u];
	for (int u = 0; u < m; u++) {
		B[u] ^= Z & B[u];
		if (!B[u].count())
			c[u] = '0';
	}
	for (int u = 0; u < m; u++)
		if (c[u] == '?') {
			bool flag = true;
			bitset<N> W = Z | B[u];
			for (int v = 0; v < m; v++) {
				for (auto x: adj[v][1])
					mark[v] |= mark[x];
				for (auto x: adj[v][0])
					mark[v] |= !W[x];
				flag &= mark[v] || c[v] != '1';
			}
			if (!flag)
				c[u] = '1';
		}
	cout << c;
}

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Incorrect 5 ms 768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Incorrect 5 ms 768 KB Output isn't correct
4 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 896 KB Output is correct
3 Incorrect 5 ms 768 KB Output isn't correct
4 Halted 0 ms 0 KB -