Submission #56414

#	Time	Username	Problem	Language	Result	Execution time	Memory
56414		polyfish	Ili (COI17_ili)	C++14	49 / 100	4006 ms	14548 KiB

ili

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 10002;
const int BITSET_SIZE = 10001; 		///notice
const int INF = 1e9;

int m, n, outcome[MAX_N], curVal[MAX_N], val[MAX_N], f[MAX_N];
vector<int> input[MAX_N];
bitset<BITSET_SIZE> subset[MAX_N];
string element_state;

void enter() {
	cin >> n >> m >> element_state;
	for (int i=1; i<=m; ++i) {
		char x1, x2;
		int L, R;
		cin >> x1 >> L >> x2 >> R;
		if (x1=='x') {
			subset[i].set(L);
			input[i].push_back(-L);
		}
		else {
			input[i].push_back(L);
		}
		if (x2=='x') {
			subset[i].set(R);
			input[i].push_back(-R);
		}
		else {
			input[i].push_back(R);
		}
	}
}

void visit(int u) {
	for (int i=0; i<input[u].size(); ++i) {
		int v = input[u][i];
		if (v>0) {
			outcome[v] = u;
			visit(v);
			subset[u] |= subset[v];
		}
	}
}

void find_0s_element() {
	bitset<BITSET_SIZE> s;
	for (int i=1; i<=m; ++i)
		if (element_state[i-1]=='0')
			s |= subset[i];
	memset(curVal, -1, sizeof(curVal));
	for (int i=1; i<=n; ++i)
		if (s.test(i))
			curVal[i] = 0;
	for (int i=1; i<=m; ++i)
		if ((s | subset[i]) == s)
			element_state[i-1] = '0';
}

int check(int u) {
	if (f[u]!=INF)
		return f[u];
	f[u] = 0;
	for (int i=0; i<input[u].size(); ++i) {
		int v = input[u][i];
		if (v<0) {
			f[u] |= val[-v];
		}
		else {
			int tmp = check(v);
			if (tmp==-1)
				return f[u] = -1;
			f[u] |= tmp;
		}
	}
	if (element_state[u-1]!='?' && element_state[u-1]-'0' != f[u])
		return f[u] = -1;
	return f[u];
}

void solve() {
	memset(outcome, -1, sizeof(outcome));
	for (int i=1; i<=m; ++i)
		if (outcome[i]==-1)
			visit(i);
	find_0s_element();
	for (int i=1; i<=m; ++i) {
		if (element_state[i-1] == '?') {
			for (int j=1; j<=n; ++j) {
				val[j] = curVal[j];
				if (subset[i].test(j))
					val[j] = 0;
				if (val[j]==-1)
					val[j] = 1;
			}
			//PR(val, n);
			bool ok = true;
			for (int i=1; i<=m; ++i)
				f[i] = INF;
			for (int i=1; i<=m; ++i) {
				if (check(i)==-1) {
					ok = false;
					break;
				}
			}
			//PR(f, m);
			if (!ok)
				element_state[i-1] = '1';
		}
	}
	cout << element_state;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	solve();
}

Compilation message (stderr)

ili.cpp: In function 'void visit(int)':
ili.cpp:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<input[u].size(); ++i) {
                ~^~~~~~~~~~~~~~~~
ili.cpp: In function 'int check(int)':
ili.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<input[u].size(); ++i) {
                ~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 0 / 51