Submission #26341

#	Time	Username	Problem	Language	Result	Execution time	Memory
26341		kdh9949	Ili (COI17_ili)	C++14	100 / 100	3899 ms	3848 KiB

ili

#include <bits/stdc++.h>
using namespace std;

int n, m, dp[20010];
char str[10010], ans[10010];
vector<int> e[20010], re[20010];

int can(){
	fill(dp + 1, dp + n + m + 1, 0);
	for(int i = n + m; i >= 1; i--){
		if(i > n){
			if(str[i - n] == '0') dp[i] = -1;
			else if(str[i - n] == '1'){
				for(auto &j : re[i]) if(dp[j] == -1) return 0;
				dp[i] = 1;
			}
			else{
				for(auto &j : re[i]) if(dp[j] == -1){ dp[i] = -1; break; }
			}
		}
		else{
			for(auto &j : re[i]) if(dp[j] == -1){ dp[i] = -1; break; }
		}
	}
	for(int i = n + 1; i <= n + m; i++){
		if(dp[i] == 1){
			if(dp[e[i][0]] == -1){
				if(dp[e[i][1]] == -1) return 0;
				dp[e[i][1]] = 1;
			}
			else if(dp[e[i][1]] == -1) dp[e[i][0]] = 1;
		}
		else if(!dp[i]){
			if(dp[e[i][0]] == 1 || dp[e[i][1]] == 1) dp[i] = 1;
			else if(dp[e[i][0]] == -1 && dp[e[i][1]] == -1) dp[i] = -1;
		}
		else{
			if(dp[e[i][0]] == 1 || dp[e[i][1]] == 1) return 0;
		}
	}
	return 1;
}

int main(){
	scanf("%d%d%s", &n, &m, str + 1);
	for(int i = 1, x, y; i <= m; i++){
		char a[10], b[10]; scanf("%s%s", &a, &b);
		sscanf(a + 1, "%d", &x);
		sscanf(b + 1, "%d", &y);
		if(a[0] == 'c') x += n;
		if(b[0] == 'c') y += n;
		e[n + i].push_back(x); e[n + i].push_back(y);
		re[x].push_back(n + i); re[y].push_back(n + i);
	}
	for(int i = 1; i <= m; i++){
		if(str[i] != '?'){
			ans[i] = str[i]; continue;
		}
		str[i] = '0';
		if(!can()){
			str[i] = '?';
			ans[i] = '1';
			continue;
		}
		str[i] = '1';
		if(can()) ans[i] = '?';
		else ans[i] = '0';
		str[i] = '?';
	}
	puts(ans + 1);
}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:47:42: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
   char a[10], b[10]; scanf("%s%s", &a, &b);
                                          ^
ili.cpp:47:42: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[10]' [-Wformat=]
ili.cpp:45:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%s", &n, &m, str + 1);
                                  ^
ili.cpp:47:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char a[10], b[10]; scanf("%s%s", &a, &b);
                                           ^

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