oj.uz

답안 #234755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
234755 2020-05-25T13:04:28 Z ArshiaDadras Ili (COI17_ili) C++14
49 / 100
 9 ms 2048 KB 
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 2e4 + 5;
vector<int> adj[N];
char c[N], C[N];
bool mark[N];
int n, m;

int read() {
	getchar();
	char x; int u;
	cin >> x >> u;
	if (x ^ 'x')
		u += n;
	return --u;
}

bool go() {
	while (true) {
		bool flag = false;
		for (int u = n + m - 1; u >= n; u--) {
			bool ok = true;
			for (auto v: adj[u])
				ok &= c[v] == '0';
			if (ok) {
				if (c[u] == '1')
					return false;
				if (c[u] == '?')
					c[u] = '0', flag = true;
			}
			if (c[u] == '0')
				for (auto v: adj[u])
					if (c[v] != '0')
						c[v] = '0', flag = true;
		}
		for (int u = n; u < n + m; u++) {
			bool ok = false;
			for (auto v: adj[u])
				ok |= c[v] == '1';
			if (ok) {
				if (c[u] == '0')
					return false;
				if (c[u] == '?')
					c[u] = '1', flag = true;
			}
		}
		if (!flag)
			break;
	}
	return true;
}

bool check(int root) {
	return c[root] = '0', go();
}

void read_input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> c[n + i];
	for (int i = 0; i < m; i++) {
		adj[n + i].push_back(read());
		adj[n + i].push_back(read());
	}
}

void solve() {
	for (int u = 0; u < n; u++)
		c[u] = '?';
	assert(go());
	for (int u = 0; u < n + m; u++)
		if (c[u] == '?') {
			copy(c, c + n + m, C);
			if (!check(u))
				C[u] = '1';
			copy(C, C + n + m, c);
			if (c[u] != '?')
				assert(go());
		}
	for (int i = 0; i < m; i++)
		cout << c[n + i];
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 7 ms 872 KB Output is correct
9 Correct 9 ms 896 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 7 ms 896 KB Output is correct
14 Correct 9 ms 896 KB Output is correct

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 7 ms 872 KB Output is correct
9 Correct 9 ms 896 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 7 ms 896 KB Output is correct
14 Correct 9 ms 896 KB Output is correct
15 Runtime error 7 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -