oj.uz

Submission #20981

# Submission time Handle Problem Language Result Execution time Memory
20981 2017-03-26T07:09:47 Z gs14004 Ili (COI17_ili) C++11
100 / 100
 3083 ms 15436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, m, l[20005], r[20005];
char str[20005];
int vis[20005];
vector<int> gph[20005];
bitset<10005> s0, s1, dod[10005];

void dfs(int x){
	if(vis[x]) return;
	vis[x] = 1;
	if(x > n){
		dfs(l[x]);
		dfs(r[x]);
	}
}

int input(){
	string s;
	cin >> s;
	int num = 0;
	for(int i=1; i<s.size(); i++){
		num = num * 10 + s[i] - '0';
	}
	if(s[0] == 'x'){
		return num;
	}
	return num + n;
}

bool p0[10005], p1[10005];

int main(){
	scanf("%d %d",&n,&m);
	scanf("%s", str + 1);
	for(int i=n+1; i<=n+m; i++){
		l[i] = input();
		r[i] = input();
		gph[l[i]].push_back(i);
		gph[r[i]].push_back(i);
	}
	for(int i=n+m; i>n; i--){
		if(!vis[i] && str[i-n] == '0'){
			dfs(i);
		}
	}
	for(int i=1; i<=n; i++){
		if(vis[i]) s0.set(i);
		else s1.set(i);
	}
	for(int i=1; i<=m; i++){
		memset(vis, 0, sizeof(vis));
		dfs(i + n);
		for(int j=1; j<=n; j++){
			if(vis[j]) dod[i].set(j);
		}
	}
	for(int i=1; i<=m; i++){
		if(str[i] == '0'){
			p0[i] = 1;
			continue;
		}
		if(str[i] == '1'){
			p1[i] = 1;
			continue;
		}
		if((dod[i] & s1).any()) p1[i] = 1;
		else p0[i] = 1, str[i] = '0';
	}
	for(int i=1; i<=m; i++){
		if(str[i] == '?' && p0[i] == 0){
			p0[i] = 1;
			queue<int> que;
			bool vis[20005] = {};
			for(int j=1; j<=n; j++){
				if(s1.test(j) && !dod[i].test(j)){
					que.push(j);
				}
			}
			while(!que.empty()){
				auto x = que.front();
				que.pop();
				for(auto &y : gph[x]){
					if(!vis[y]){
						vis[y] = 1;
						que.push(y);
					}
				}
			}
			for(int j=1; j<=m; j++){
				if(str[j] == '1' && !vis[j + n]){
					p0[i] = 0;
					break;
				}
			}
		}
		if(p0[i] && p1[i]) putchar('?');
		else if(p0[i]) putchar('0');
		else putchar('1');
	}
}

Compilation message

ili.cpp: In function 'int input()':
ili.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<s.size(); i++){
                ^
ili.cpp: In function 'int main()':
ili.cpp:38:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
ili.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str + 1);
                      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15040 KB Output is correct
2 Correct 0 ms 15040 KB Output is correct
3 Correct 0 ms 15040 KB Output is correct
4 Correct 0 ms 15040 KB Output is correct
5 Correct 0 ms 15040 KB Output is correct
6 Correct 0 ms 15040 KB Output is correct
7 Correct 0 ms 15040 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15040 KB Output is correct
2 Correct 0 ms 15040 KB Output is correct
3 Correct 0 ms 15040 KB Output is correct
4 Correct 0 ms 15040 KB Output is correct
5 Correct 0 ms 15040 KB Output is correct
6 Correct 0 ms 15040 KB Output is correct
7 Correct 0 ms 15040 KB Output is correct
8 Correct 6 ms 15040 KB Output is correct
9 Correct 3 ms 15040 KB Output is correct
10 Correct 3 ms 15040 KB Output is correct
11 Correct 3 ms 15040 KB Output is correct
12 Correct 3 ms 15040 KB Output is correct
13 Correct 3 ms 15040 KB Output is correct
14 Correct 6 ms 15040 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15040 KB Output is correct
2 Correct 0 ms 15040 KB Output is correct
3 Correct 0 ms 15040 KB Output is correct
4 Correct 0 ms 15040 KB Output is correct
5 Correct 0 ms 15040 KB Output is correct
6 Correct 0 ms 15040 KB Output is correct
7 Correct 0 ms 15040 KB Output is correct
8 Correct 6 ms 15040 KB Output is correct
9 Correct 3 ms 15040 KB Output is correct
10 Correct 3 ms 15040 KB Output is correct
11 Correct 3 ms 15040 KB Output is correct
12 Correct 3 ms 15040 KB Output is correct
13 Correct 3 ms 15040 KB Output is correct
14 Correct 6 ms 15040 KB Output is correct
15 Correct 523 ms 15172 KB Output is correct
16 Correct 1093 ms 15304 KB Output is correct
17 Correct 766 ms 15304 KB Output is correct
18 Correct 3009 ms 15304 KB Output is correct
19 Correct 843 ms 15304 KB Output is correct
20 Correct 2209 ms 15436 KB Output is correct
21 Correct 3083 ms 15436 KB Output is correct
22 Correct 596 ms 15436 KB Output is correct
23 Correct 666 ms 15436 KB Output is correct
24 Correct 656 ms 15436 KB Output is correct
25 Correct 509 ms 15176 KB Output is correct
26 Correct 523 ms 15176 KB Output is correct
27 Correct 553 ms 15176 KB Output is correct
28 Correct 473 ms 15176 KB Output is correct
29 Correct 513 ms 15176 KB Output is correct
30 Correct 519 ms 15176 KB Output is correct
31 Correct 406 ms 15328 KB Output is correct
32 Correct 549 ms 15312 KB Output is correct