oj.uz

Submission #26292

# Submission time Handle Problem Language Result Execution time Memory
26292 2017-06-29T05:33:37 Z 김동현(#1101) Ili (COI17_ili) C++14
0 / 100
 0 ms 4460 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, c[10010][2], vis[40010], cnt, po[40010], cn[40010];
char str[10010], ans[10010];
vector<int> e[40010], re[40010];

void add(int x, int y){
	e[x].push_back(y);
	e[y ^ 1].push_back(x ^ 1);
	re[y].push_back(x);
	re[x ^ 1].push_back(y ^ 1);
}

void f(int x){
	vis[x] = 1;
	for(auto &i : e[x]) if(!vis[i]) f(i);
	po[++cnt] = x;
}

void rf(int x){
	cn[x] = cnt;
	vis[x] = 1;
	for(auto &i : re[x]) if(!vis[i]) rf(i);
}

int can(){
	for(int i = 0; i < 2 * (n + m); i++){ e[i].clear(); re[i].clear(); }
	for(int i = 1; i <= m; i++){
		add(2 * c[i][0] - 1, 2 * (n + i) - 1);
		add(2 * c[i][1] - 1, 2 * (n + i) - 1);
		if(str[i] == '1') add(2 * c[i][0] - 2, 2 * c[i][1] - 1);
		else if(str[i] == '0'){
			add(2 * c[i][0] - 1, 2 * c[i][0] - 2);
			add(2 * c[i][1] - 1, 2 * c[i][1] - 2);
			add(2 * (n + i) - 1, 2 * (n + i) - 2);
		}
	}
	fill(vis, vis + 2 * (n + m), 0); cnt = 0;
	for(int i = 0; i < 2 * (n + m); i++) if(!vis[i]) f(i);
	fill(vis, vis + 2 * (n + m), 0); cnt = 0;
	for(int i = 2 * (n + m); i >= 1; i--){
		if(!vis[po[i]]){ cnt++; rf(po[i]); }
	}
	for(int i = 1; i <= n + m; i++){
		if(cn[2 * i - 2] == cn[2 * i - 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;
		c[i][0] = x; c[i][1] = y;
	}
	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

ili.cpp: In function 'int main()':
ili.cpp:54: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:54:42: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[10]' [-Wformat=]
ili.cpp:52: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:54: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4460 KB Output is correct
2 Correct 0 ms 4460 KB Output is correct
3 Incorrect 0 ms 4460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4460 KB Output is correct
2 Correct 0 ms 4460 KB Output is correct
3 Incorrect 0 ms 4460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4460 KB Output is correct
2 Correct 0 ms 4460 KB Output is correct
3 Incorrect 0 ms 4460 KB Output isn't correct
4 Halted 0 ms 0 KB -