Submission #234724

#	Time	Username	Problem	Language	Result	Execution time	Memory
234724		ArshiaDadras	Ili (COI17_ili)	C++17	0 / 100	6 ms	1408 KiB

ili

/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;

const int N = 2e4 + 5;
vector<int> adj[N];
bool mark[N];
int n, m;
char c[N];

void read(char &x, int &u) {
	scanf("%c%d", &x, &u);
	if (x ^ 'x')
		u += n;
	getchar();
}

bool check(int root) {
	c[root] = '0';
	mark[root] = true;
	for (int u = n + m - 1; u >= n; u--) {
		if (mark[u])
			for (auto v: adj[u])
				if (c[v] == '?') {
					mark[v] = true;
					c[v] = '0';
				}
		bool one = false;
		for (auto v: adj[u])
			one |= c[v] != '0';
		if (c[u] ^ '?' && c[u] - '0' ^ one)
			return false;
	}
	return true;
}

void read_input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> c[n + i];
	for (int i = 0; i < m; i++) {
		int u, v; char x, y;
		read(x, u), read(y, v);
		adj[n + i].push_back(--u);
		adj[n + i].push_back(--v);
	}
}

void solve() {
	for (int u = 0; u < n; u++)
		c[u] = '?';
	for (int u = n + m - 1; u >= n; u--)
		if (c[u] == '0')
			for (auto v: adj[u])
				c[v] = '0';
	for (int u = 0; u < n + m; u++) {
		if (c[u] == '?' && !check(u)) {
			mark[u] = false;
			c[u] = '1';
		}
		for (int v = 0; v < n + m; v++)
			if (mark[v]) {
				mark[v] = false;
				c[v] = '?';
			}
	}
	for (int i = 0; i < m; i++)
		cout << c[n + i];
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}

Compilation message (stderr)

ili.cpp: In function 'bool check(int)':
ili.cpp:31:26: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   if (c[u] ^ '?' && c[u] - '0' ^ one)
                     ~~~~~^~~~~
ili.cpp: In function 'void read(char&, int&)':
ili.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c%d", &x, &u);
  ~~~~~^~~~~~~~~~~~~~~~

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