Submission #232299

#	Time	Username	Problem	Language	Result	Execution time	Memory
232299		pedy4000	Ili (COI17_ili)	C++14	49 / 100	4046 ms	14840 KiB

ili

#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
#include <unordered_map>
using namespace std;

const int N = 1e4 + 8, MOD = 1e9 + 7;
int pw[N];
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;
unordered_map <int, bool> Map;

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);
	pw[0] = 1;
	for (int i = 1; i < N; i++)
		pw[i] = (2 * pw[i - 1]) % MOD;
	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;
		}
		if (bt[i].count() == 0)
			type[i] = 0;
	}

	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] != 1)
			continue;
		int val = 0;
		for (int j = 0; j < n; j++)
			if (bt[i][j])
				val = (val + pw[j]) % MOD;
		Map[val] = true;
	}

	for (int i = 0; i < m; i++) {
		if (type[i] != 2)
			continue;
		int val = 0;
		for (int j = 0; j < n; j++)
			if (bt[i][j])
				val = (val + pw[j]) % MOD;

		if (Map[val])
			type[i] = 1;
		if (type[in[i][0]] == 1 || type[in[i][1]] == 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: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 0 / 51