oj.uz

Submission #56416

# Submission time Handle Problem Language Result Execution time Memory
56416 2018-07-11T09:11:16 Z polyfish Ili (COI17_ili) C++14
49 / 100
 4000 ms 13696 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, 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];
}

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() {
	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;
			}
			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 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) {
                ~^~~~~~~~~~~~~~~~
ili.cpp: In function 'bool check()':
ili.cpp:93: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 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 1036 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 1036 KB Output is correct
8 Correct 5 ms 1468 KB Output is correct
9 Correct 4 ms 1468 KB Output is correct
10 Correct 5 ms 1468 KB Output is correct
11 Correct 6 ms 1596 KB Output is correct
12 Correct 3 ms 1596 KB Output is correct
13 Correct 3 ms 1596 KB Output is correct
14 Correct 6 ms 1596 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 1036 KB Output is correct
8 Correct 5 ms 1468 KB Output is correct
9 Correct 4 ms 1468 KB Output is correct
10 Correct 5 ms 1468 KB Output is correct
11 Correct 6 ms 1596 KB Output is correct
12 Correct 3 ms 1596 KB Output is correct
13 Correct 3 ms 1596 KB Output is correct
14 Correct 6 ms 1596 KB Output is correct
15 Correct 55 ms 8572 KB Output is correct
16 Correct 390 ms 9888 KB Output is correct
17 Correct 172 ms 11660 KB Output is correct
18 Correct 844 ms 13540 KB Output is correct
19 Correct 270 ms 13540 KB Output is correct
20 Correct 1038 ms 13612 KB Output is correct
21 Correct 1175 ms 13696 KB Output is correct
22 Correct 3421 ms 13696 KB Output is correct
23 Execution timed out 4009 ms 13696 KB Time limit exceeded
24 Halted 0 ms 0 KB -