| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 209734 | parsa_mobed | Ili (COI17_ili) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
int a[N], lp[N], rp[N];
vector <int> Out[N];
bitset <N> reach[N], good[N], tmp, bt;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
memset(a, -1, sizeof a);
for (int i = 1; i <= m; i++) {
char c; cin >> c;
if (c == '1') a[i + n] = 1;
if (c == '0') a[i + n] = 0;
}
for (int i = 1; i <= m; i++) {
char c1, c2; int v1, v2; cin >> c1 >> v1 >> c2 >> v2;
if (c1 == 'x') Out[v1].push_back(i + n), lp[i + n] = v1;
else Out[v1 + n].push_back(i + n), lp[i + n] = v1 + n;
if (c2 == 'x') Out[v2].push_back(i + n), rp[i + n] = v2;
else Out[v2 + n].push_back(i + n), rp[i + n] = v2 + n;
}
for (int i = n + m; i >= 1; i--) {
reach[i][i] = 1;
for (int u : Out[i]) {
reach[i] |= reach[u];
if (a[u] == 0) a[i] = 0;
}
}
for (int i = 1; i <= n + m; i++) {
if (a[lp[i]] == 0 && a[rp[i]] == 0) a[i] = 0;
if (a[i] == 0) bt[i] = 1;
}
for (int i = 1; i <= n + m; i++) if (a[i] == 1) good[lp[i]][rp[i]] = good[rp[i]][lp[i]] = 1;
for (int i = 1; i <= n + m; i++) for (int j = 1; j <= n + m; j++) {
good[i][j] |= good[lp[i]][j] | good[rp[i]][j] | good[i][lp[j]] | good[i][rp[j]];
}
for (int i = 1; i <= n + m; i++) {
if (a[lp[i]] == 1 || a[rp[i]] == 1 || good[lp[i]][rp[i]] == 1 || good[i][i] == 1) a[i] = 1;
tmp = good[i] & bt;
if (tmp.count() > 0) a[i] = 1;
}
for (int i = n + 1; i <= n + m; i++) {
if (a[i] == -1) cout << '?';
else cout << a[i];
}
cout << "\n";
return 0;
}