Submission #234773

#	Time	Username	Problem	Language	Result	Execution time	Memory
234773		ArshiaDadras	Ili (COI17_ili)	C++14	100 / 100	608 ms	13944 KiB

ili

/* 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++) {
				mark[v] = false;
				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: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51