Submission #234773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
234773	2020-05-25T14:05:41 Z	ArshiaDadras	Ili (COI17_ili)	C++14	100 / 100	608 ms	13944 KB

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.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	896 KB	Output is correct
5	Correct	5 ms	896 KB	Output is correct
6	Correct	5 ms	896 KB	Output is correct
7	Correct	5 ms	896 KB	Output is correct

Subtask #2

42.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	896 KB	Output is correct
5	Correct	5 ms	896 KB	Output is correct
6	Correct	5 ms	896 KB	Output is correct
7	Correct	5 ms	896 KB	Output is correct
8	Correct	6 ms	1408 KB	Output is correct
9	Correct	6 ms	1280 KB	Output is correct
10	Correct	6 ms	1408 KB	Output is correct
11	Correct	6 ms	1408 KB	Output is correct
12	Correct	6 ms	1408 KB	Output is correct
13	Correct	6 ms	1408 KB	Output is correct
14	Correct	8 ms	1408 KB	Output is correct

Subtask #3

51.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	896 KB	Output is correct
5	Correct	5 ms	896 KB	Output is correct
6	Correct	5 ms	896 KB	Output is correct
7	Correct	5 ms	896 KB	Output is correct
8	Correct	6 ms	1408 KB	Output is correct
9	Correct	6 ms	1280 KB	Output is correct
10	Correct	6 ms	1408 KB	Output is correct
11	Correct	6 ms	1408 KB	Output is correct
12	Correct	6 ms	1408 KB	Output is correct
13	Correct	6 ms	1408 KB	Output is correct
14	Correct	8 ms	1408 KB	Output is correct
15	Correct	159 ms	8448 KB	Output is correct
16	Correct	317 ms	9976 KB	Output is correct
17	Correct	362 ms	11768 KB	Output is correct
18	Correct	603 ms	13692 KB	Output is correct
19	Correct	274 ms	9984 KB	Output is correct
20	Correct	608 ms	13688 KB	Output is correct
21	Correct	591 ms	13696 KB	Output is correct
22	Correct	169 ms	13048 KB	Output is correct
23	Correct	195 ms	13560 KB	Output is correct
24	Correct	184 ms	13440 KB	Output is correct
25	Correct	262 ms	13464 KB	Output is correct
26	Correct	207 ms	13312 KB	Output is correct
27	Correct	211 ms	13432 KB	Output is correct
28	Correct	197 ms	13048 KB	Output is correct
29	Correct	237 ms	13184 KB	Output is correct
30	Correct	244 ms	13304 KB	Output is correct
31	Correct	214 ms	13944 KB	Output is correct
32	Correct	225 ms	13824 KB	Output is correct