Submission #545226

#	Time	Username	Problem	Language	Result	Execution time	Memory
545226		hollwo_pelw	Ili (COI17_ili)	C++17	100 / 100	468 ms	412 KiB

ili

#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() {
	char s; int v; cin >> s >> v;
	return v + (s == 'c' ? 1 : 0) * n;
}

inline void upd0(bitset<N> &a, int p) {
	for (; p > n; p --)
		if (!a[p]) a[prv[p][0]] = a[prv[p][1]] = 0;
}

inline void upd1(bitset<N> &a) {
	for (int p = n + 1; p <= n + m; p++)
		a[p] = a[prv[p][0]] | a[prv[p][1]];
}

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();
		
		// cout << a << ' ' << b << '\n';

		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);
	
	upd0(a, n + m), upd1(a);

	// for (int i = 1; i <= n + m; i++)
	// 	cout << a[i] << " \n"[i == n + m];

	for (int i = n + 1; i <= n + m; i++)
		if (c[i] == '?' && a[i]) {
			b = a, b.set(i, 0);
			
			upd0(b, i), upd1(b);

			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++) {
		if (c[i] != '?')
			cout << c[i];
		else
			cout << (a[i] == 0 ? '0' : c[i]);
	}
}

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