oj.uz

답안 #660724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660724 2022-11-22T21:56:09 Z Kahou Ili (COI17_ili) C++14
100 / 100
 1841 ms 856 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 20050;
int n, m, val[N], val2[N];
bool vis[N];
int adjM[N][2];
vector<int> vc;

void dfs(int u) {
	vis[u] = 1;
	if (u>n) for (int v:adjM[u]) {
		if (vis[v]) continue;
		dfs(v);
	}
	vc.push_back(u);
}

void sfd(int u) {
	val[u] = 0;
	if (u>n) for (int v:adjM[u]) {
		sfd(v);
	}
}
void sfd2(int u) {
	val2[u] = 0;
	if (u>n) for (int v:adjM[u]) {
		sfd2(v);
	}
}
bool check(int u) {
	for (int v = 1; v <= n+m; v++) val2[v] = val[v];
	sfd2(u);
	
	for (int v:vc) {
		bool f1 = 0, f2 = 0;
		if(v>n) for (int x:adjM[v]) {
			f1 = f1||(val2[x] == 1);
			f2 = f2||(val2[x]);
		}
		if (f1) val2[v] = 1;
		else if (!f2 && v > n) val2[v] = 0;
		if (val2[v] != 2 && val[v] != 2 && val[v] != val2[v]) return 0;
	}
	return 1;
}

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) val[i] = 2;
	for (int i = n+1; i <= n+m; i++) {
		char c;
		cin >> c;
		val[i] = (c!='0')+(c=='?');
	}
	for (int v = n+1; v <= n+m; v++) {
		char c1, c2;
		int n1, n2;
		cin >> c1>>n1 >> c2>>n2;
		int u1 = (c1=='c')*n + n1;
		int u2 = (c2=='c')*n + n2;
		adjM[v][0] = u1;
		adjM[v][1] = u2;
	}
	for (int u = 1; u <= n+m; u++) {
		if (!vis[u]) dfs(u);
	}

	for (int u:vc) {
		if (!val[u]) sfd(u);
	}

	for (int u:vc) {
		if (!check(u)) val[u] = 1;
		else if (u > n) {
			bool flg = 0;
			for (int v:adjM[u]) {
				flg = flg||(val[v]);
			}
			if(!flg) val[u] = 0;
		}
	}
	for (int i = 1; i <= m; i++) {
		cout << (char)(val[n+i] < 2? '0'+val[n+i] :'?');
	}
}
int main() {
	solve();
	return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 312 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 115 ms 532 KB Output is correct
16 Correct 476 ms 608 KB Output is correct
17 Correct 453 ms 648 KB Output is correct
18 Correct 761 ms 724 KB Output is correct
19 Correct 580 ms 620 KB Output is correct
20 Correct 1667 ms 756 KB Output is correct
21 Correct 1841 ms 856 KB Output is correct
22 Correct 482 ms 752 KB Output is correct
23 Correct 524 ms 724 KB Output is correct
24 Correct 493 ms 764 KB Output is correct
25 Correct 418 ms 764 KB Output is correct
26 Correct 424 ms 776 KB Output is correct
27 Correct 433 ms 764 KB Output is correct
28 Correct 374 ms 760 KB Output is correct
29 Correct 391 ms 756 KB Output is correct
30 Correct 428 ms 764 KB Output is correct
31 Correct 278 ms 696 KB Output is correct
32 Correct 394 ms 724 KB Output is correct