oj.uz

Submission #232255

# Submission time Handle Problem Language Result Execution time Memory
232255 2020-05-16T14:09:07 Z pedy4000 Ili (COI17_ili) C++14
0 / 100
 6 ms 1280 KB 
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int N = 1e4 + 8;
int n, m;
string s;
int type[N * 2];
bool mark[N * 2];
bitset <N> bt[N];
vector <int> in[N * 2], out[N * 2];
vector <int> one;

void set0 (int d) {
	mark[d] = true;
	type[d] = 0;
	for (int v: in[d])
		if (!mark[v])
			set0(v);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++)
		type[i] = (s[i] == '?'? 2: s[i] - '0');
	for (int i = m; i < m + n; i++)
		type[i] = 2;

	for (int i = 0; i < m; i++)
		for (int j = 0; j < 2; j++) {
			char c;
			int ind;
			cin >> c >> ind;
			ind--;
			if (c == 'x')
				ind += m;

			in[i].push_back(ind);
			out[ind].push_back(i);
		}

	for (int i = 0; i < m + n; i++)
		if (type[i] == 0 && !mark[i])
			set0(i);

	for (int i = 0; i < m + n; i++)
		mark[i] = 0;

	for (int i = 0; i < m; i++) {
		if (type[i] == 0)
			continue;

		for (int v: in[i]) {
			if (type[v] == 0)
				continue;

			if (m <= v)
				bt[i][v - m] = true;
			else
				bt[i] |= bt[v];

			if (type[v] == 1)
				type[i] = 1;
		}
	}

	for (int i = m - 1; ~i; i--) {
		if (type[i] != 1)
			continue;
		if (type[in[i][0]] == 1 || type[in[i][1]] == 1)
			continue;
		if (type[in[i][0]] == 2 || type[in[i][1]] == 2) {
			one.push_back(i);
			continue;
		}

		if (type[in[i][0]] == 0)
			type[in[i][1]] = 1;
		else
			type[in[i][0]] = 1;
	}

	for (int i = 0; i < m; i++) {
		if (type[i] != 2)
			continue;
		if (type[in[i][0]] == 1 || type[in[i][1]] == 1) {
			type[i] = 1;
			continue;
		}
		if (type[in[i][0]] == 0 || type[in[i][1]] == 0)
			continue;
		
		for (int v: one)
			if ((bt[i] & bt[v]) == bt[v]) {
				type[i] = 1;
				break;
			}
	}

	for (int i = 0; i < m; i++)
		cout << (type[i] == 2? '?': char('0' + type[i]));
	return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 42.0

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

Subtask #3
0 / 51.0

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