Submission #250811

#TimeUsernameProblemLanguageResultExecution timeMemory
250811NONAMEIli (COI17_ili)C++14
49 / 100
4099 ms889864 KiB
#include <bits/stdc++.h> #define dbg(x) cerr << #x << " = " << x << "\n" #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie() using namespace std; using ll = long long; const int N = int(2e4) + 500; int n, m; array <int, 2> a[N]; vector <int> g[N]; bool mk[N], m0[N], m1[N]; string s; set <int> n1, vis[N]; void dfs(int v) { if (mk[v]) return; mk[v] = 1; if (v <= n) return; dfs(a[v][0]); dfs(a[v][1]); } int input() { string t; cin >> t; int len = int(t.size()), res = 0; for (int i = 1; i < len; ++i) (res *= 10) += (t[i] - '0'); if (t[0] == 'c') return res + n; return res; } int main() { fast_io; cin >> n >> m; cin >> s; s = "*" + s; for (int i = n + 1; i <= n + m; ++i) { a[i] = {input(), input()}; g[a[i][0]].push_back(i); g[a[i][1]].push_back(i); } for (int i = n + 1; i <= n + m; ++i) if (s[i - n] == '0') dfs(i); for (int i = 1; i <= n; ++i) if (!mk[i]) n1.insert(i); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n + m; ++j) mk[j] = 0; dfs(i + n); for (int j = 1; j <= n; ++j) if (mk[j]) vis[i].insert(j); } for (int i = 1; i <= m; ++i) { if (s[i] == '0') { m0[i] = 1; continue; } if (s[i] == '1') { m1[i] = 1; continue; } for (auto j : n1) if (vis[i].count(j)) m1[i] = 1; if (!m1[i]) m0[i] = 1, s[i] = '0'; } for (int i = 1; i <= m; ++i) { if (s[i] == '?') { m0[i] = 1; for (int j = 1; j <= n + m; ++j) mk[j] = 0; queue <int> q; for (auto j : n1) if (!vis[i].count(j)) q.push(j); while (!q.empty()) { int v = q.front(); q.pop(); for (auto u : g[v]) if (!mk[u]) { mk[u] = 1; q.push(u); } } for (int j = 1; j <= m; ++j) if (s[j] == '1' && !mk[j + n]) m0[i] = 0; } if (m0[i] && m1[i]) cout << "?"; else if (m0[i]) cout << "0"; else cout << "1"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...