oj.uz

Submission #545224

# Submission time Handle Problem Language Result Execution time Memory
545224 2022-04-04T04:09:38 Z hollwo_pelw Ili (COI17_ili) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen("A.inp", "r"))
		assert(freopen("A.inp", "r", stdin)), assert(freopen("A.out", "w", stdout));
#else
	auto start = chrono::steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 2e4 + 5;

int n, m, prv[N][2];
char c[N];

inline int read() {
	string s; cin >> s;
	int t = s[0] == 'x' ? 0 : 1, v = 0;
	s = s.substr(1);
	stringstream ss;
	ss << s; ss >> v;
	return v + t * n;
}

inline char _or(char a, char b) {
	if (a == '1' || b == '1') return '1';
	if (a == '0' && b == '0') return '0';
	return '?';
}

void Hollwo_Pelw(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		c[i] = '?';
	for (int i = n + 1; i <= n + m; i++)
		cin >> c[i];

	for (int i = n + 1; i <= n + m; i++) {
		int a = read(), b = read();
		
		prv[i][0] = a;
		prv[i][1] = b;
	}

	bitset<N> a, b;
	for (int i = 1; i <= n + m; i++)
		a.set(i, c[i] == '0' ? 0 : 1);
	
	for (int i = n + m; i > n; i--)
		if (!a[i]) a[prv[i][0]] = a[prv[i][1]] = 0;
	for (int i = n + 1; i <= n + m; i++)
		a[i] = a[prv[i][0]] | a[prv[i][1]];

	for (int i = n + 1; i <= n + m; i++)
		if (c[i] == '?' && a[i]) {
			b = a, b.set(i, 0);
			for (int j = i; j > n; j--)
				if (!b[j]) b[prv[j][0]] = b[prv[j][1]] = 0;
			for (int j = n + 1; j <= n + m; j++)
				b[j] = b[prv[j][0]] | b[prv[j][1]];

			for (int j = n + 1; j <= n + m; j++)
				if (c[j] == '1' && !b[j]) c[i] = '1';
		}

	for (int i = n + 1; i <= n + m; i++)
		cout << c[i];
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 42.0

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

Subtask #3
0 / 51.0

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