oj.uz

Submission #56496

# Submission time Handle Problem Language Result Execution time Memory
56496 2018-07-11T13:36:53 Z polyfish Ili (COI17_ili) C++14
100 / 100
 1310 ms 15248 KB 
//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, 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 init_subset() {
	for (int u=1; u<=m; ++u) {
		for (int i=0; i<input[u].size(); ++i) {
			int v = input[u][i];
			if (v>0)
				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];
}

bool check() {
	for (int u=1; u<=m; ++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
				f[u] |= f[v];
		}
		if (element_state[u-1]!='?' && element_state[u-1]-'0'!=f[u])
			return false;
	}
	return true;
}

void solve() {
	init_subset();
	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;
			}
			if (!check())
				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

ili.cpp: In function 'void init_subset()':
ili.cpp:46:18: 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:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<input[u].size(); ++i) {
                ~^~~~~~~~~~~~~~~~
ili.cpp: In function 'bool check()':
ili.cpp:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<input[u].size(); ++i) {
                 ~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 4 ms 636 KB Output is correct
3 Correct 4 ms 816 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 3 ms 868 KB Output is correct
6 Correct 4 ms 868 KB Output is correct
7 Correct 2 ms 868 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 4 ms 636 KB Output is correct
3 Correct 4 ms 816 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 3 ms 868 KB Output is correct
6 Correct 4 ms 868 KB Output is correct
7 Correct 2 ms 868 KB Output is correct
8 Correct 4 ms 1488 KB Output is correct
9 Correct 0 ms 1488 KB Output is correct
10 Correct 5 ms 1488 KB Output is correct
11 Correct 6 ms 1488 KB Output is correct
12 Correct 3 ms 1488 KB Output is correct
13 Correct 4 ms 1488 KB Output is correct
14 Correct 5 ms 1488 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 4 ms 636 KB Output is correct
3 Correct 4 ms 816 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 3 ms 868 KB Output is correct
6 Correct 4 ms 868 KB Output is correct
7 Correct 2 ms 868 KB Output is correct
8 Correct 4 ms 1488 KB Output is correct
9 Correct 0 ms 1488 KB Output is correct
10 Correct 5 ms 1488 KB Output is correct
11 Correct 6 ms 1488 KB Output is correct
12 Correct 3 ms 1488 KB Output is correct
13 Correct 4 ms 1488 KB Output is correct
14 Correct 5 ms 1488 KB Output is correct
15 Correct 46 ms 8528 KB Output is correct
16 Correct 395 ms 9992 KB Output is correct
17 Correct 187 ms 11912 KB Output is correct
18 Correct 846 ms 13676 KB Output is correct
19 Correct 311 ms 13676 KB Output is correct
20 Correct 1154 ms 13740 KB Output is correct
21 Correct 1310 ms 14008 KB Output is correct
22 Correct 289 ms 14008 KB Output is correct
23 Correct 229 ms 14008 KB Output is correct
24 Correct 285 ms 14148 KB Output is correct
25 Correct 560 ms 14168 KB Output is correct
26 Correct 467 ms 14168 KB Output is correct
27 Correct 438 ms 14412 KB Output is correct
28 Correct 417 ms 14412 KB Output is correct
29 Correct 380 ms 14600 KB Output is correct
30 Correct 408 ms 14756 KB Output is correct
31 Correct 426 ms 15136 KB Output is correct
32 Correct 471 ms 15248 KB Output is correct