oj.uz

Submission #66571

# Submission time Handle Problem Language Result Execution time Memory
66571 2018-08-11T13:22:50 Z ekrem Ili (COI17_ili) C++
0 / 100
 6 ms 4332 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

int n, m, a[N], aa[N];
pair < int , int > g[N];

void yap(){
	for(int i = n + m; i > n; i--){
		if(a[i] == 0 and a[g[i].st] <= 0 and a[g[i].nd] <= 0){
			a[g[i].st] = 0;
			a[g[i].nd] = 0;
		}
		if(a[g[i].st] == 0 and a[g[i].nd] == 0 and a[i] != 1)
			a[i] = 0;
		if((a[g[i].st] == 1 or a[g[i].nd] == 1) and a[i] != 0)
			a[i] = 1;
		if(a[i] == 1 and a[g[i].st] == 0 and a[g[i].nd] != 0)
			a[g[i].nd] = 1;
		if(a[i] == 1 and a[g[i].nd] == 0 and a[g[i].st] != 0)
			a[g[i].st] = 1;
		// cout << a[i] << " -> " << a[g[i].st] << " , " << a[g[i].nd] << endl;
	}
}

int orla(int i){
	if(a[g[i].st] == 0 and a[g[i].nd] == 0)
		return 0;
	if(a[g[i].st] == 1 or a[g[i].nd] == 1)
		return 1;
	return -1;
}

// int zorla(int i){
// 	if(aa[g[i].st] == 0 and aa[g[i].nd] == 0)
// 		return 0;
// 	if(aa[g[i].st] == 1 or aa[g[i].nd] == 1)
// 		return 1;
// 	return -1;
// }

bool bak(int t){
	for(int i = 1; i <= n + m; i++)
		aa[i] = a[i];
	aa[t] = 0;
	for(int i = t; i > n; i--){
		if(aa[i] == 0){
			if(aa[g[i].st] == 1 or aa[g[i].nd] == 1)return -1;
			aa[g[i].st] = 0;
			aa[g[i].nd] = 0;
		}
	}
	for(int i = n + 1; i <= n + m; i++){
		if(aa[i] != -1){
			if(aa[i] == 1 and aa[g[i].st] == 0 and aa[g[i].nd] == 0)
				return 0;
			if(aa[i] == 0 and (aa[g[i].st] == 1 or aa[g[i].st] == 1))
				return 0;
		}else{
			if(aa[g[i].st] == 0 and aa[g[i].nd] == 0)
				aa[i] = 0;
			if((aa[g[i].st] == 1 or aa[g[i].st] == 1))
				aa[i] = 1;
		}
	}
	return 1;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);

	memset(a, -1, sizeof a);

	for(int i = 1; i <= m; i++){
		char x;
		scanf(" %c",&x);
		if(x == '1')
			a[i + n] = 1;
		if(x == '0')
			a[i + n] = 0;
	}

	for(int i = 1; i <= m; i++){
		int x, y;
		char aa, b;
		scanf(" %c%d %c%d",&aa ,&x ,&b ,&y);
		if(aa == 'c')
			x += n;
		if(b == 'c')
			y += n;
		g[i + n].st = x;
		g[i + n].nd = y;
		// cout << i + n << " -> " << x << " , " << y << endl;
		// cout << a[i + n] << " -> " << a[x] << " , " << a[y] << endl;
	}

	// yap();
	for(int i = n + m; i > n; i--)
		if(a[i] == 0)
			a[g[i].st] = a[g[i].nd] = 0;

	for(int i = n + m; i > n; i--)
		if(a[i] == -1)
			a[i] = orla(i);

	// for(int i = 1; i <= n + m; i++)
	// 	aa[i] = a[i];

	// for(int i = n + 1; i <= n + m; i++)if(a[i] != -1)printf("%d",a[i]);else printf("?");puts("");
	for(int i = n + 1; i <= n + m; i++)
		if(a[i] == -1){
			// for(int i = 1; i <= n + m; i++)
			// 		a[i] = aa[i];
			// cout << i << " -> " << f << endl;
			// 	cout << bak(i)<<" ";
			// for(int i = n + 1; i <= n + m; i++)if(a[i] != -1)printf("%d",a[i]);else printf("?");puts("");
			if(!bak(i))
				a[i] = 1;
		}
	for(int i = n + 1; i <= n + m; i++)
		if(a[i] != -1)
			printf("%d",a[i]);
		else
			printf("?");

	return 0;
}

Compilation message

ili.cpp: In function 'int main()':
ili.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&m);
  ~~~~~^~~~~~~~~~~~~~~~
ili.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&x);
   ~~~~~^~~~~~~~~~
ili.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d %c%d",&aa ,&x ,&b ,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 42.0

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

Subtask #3
0 / 51.0

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