oj.uz

답안 #232283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232283 2020-05-16T14:32:28 Z pedy4000 Ili (COI17_ili) C++14
7 / 100
 7 ms 1920 KB 
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int N = 1e4 + 8;
int n, m;
string s;
int type[N * 2];
bool mark[N * 2];
bitset <N> bt[N];
vector <int> in[N * 2], out[N * 2];
vector <int> one;

void set0 (int d) {
	mark[d] = true;
	type[d] = 0;
	for (int v: in[d])
		if (!mark[v])
			set0(v);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++)
		type[i] = (s[i] == '?'? 2: s[i] - '0');
	for (int i = m; i < m + n; i++)
		type[i] = 2;

	for (int i = 0; i < m; i++)
		for (int j = 0; j < 2; j++) {
			char c;
			int ind;
			cin >> c >> ind;
			ind--;
			if (c == 'x')
				ind += m;

			in[i].push_back(ind);
			out[ind].push_back(i);
		}

	for (int i = 0; i < m + n; i++)
		if (type[i] == 0 && !mark[i])
			set0(i);

	for (int i = 0; i < m + n; i++)
		mark[i] = 0;

	for (int i = 0; i < m; i++) {
		if (type[i] == 0)
			continue;

		for (int v: in[i]) {
			if (type[v] == 0)
				continue;

			if (m <= v)
				bt[i][v - m] = true;
			else
				bt[i] |= bt[v];

			if (type[v] == 1)
				type[i] = 1;
		}
		if (bt[i].count() == 0)
			type[i] = 0;
	}

	for (int i = m - 1; ~i; i--) {
		if (type[i] != 1)
			continue;
		if (type[in[i][0]] == 1 || type[in[i][1]] == 1)
			continue;
		if (type[in[i][0]] == 2 && type[in[i][1]] == 2) {
			one.push_back(i);
			continue;
		}

		if (type[in[i][0]] == 0)
			type[in[i][1]] = 1;
		else
			type[in[i][0]] = 1;
	}

	for (int i = 0; i < m; i++) {
		if (type[i] != 2)
			continue;
		if (type[in[i][0]] == 1 || type[in[i][1]] == 1) {
			type[i] = 1;
			continue;
		}
		if (type[in[i][0]] == 0 || type[in[i][1]] == 0)
			continue;
		
		for (int v: one)
			if ((bt[i] & bt[v]) == bt[v]) {
				type[i] = 1;
				break;
			}
	}

	for (int i = 0; i < m; i++)
		cout << (type[i] == 2? '?': char('0' + type[i]));
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 6 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 6 ms 1896 KB Output is correct
9 Correct 7 ms 1792 KB Output is correct
10 Correct 7 ms 1920 KB Output is correct
11 Correct 6 ms 1920 KB Output is correct
12 Correct 6 ms 1920 KB Output is correct
13 Incorrect 7 ms 1920 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 6 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 6 ms 1896 KB Output is correct
9 Correct 7 ms 1792 KB Output is correct
10 Correct 7 ms 1920 KB Output is correct
11 Correct 6 ms 1920 KB Output is correct
12 Correct 6 ms 1920 KB Output is correct
13 Incorrect 7 ms 1920 KB Output isn't correct
14 Halted 0 ms 0 KB -