Submission #232288

#TimeUsernameProblemLanguageResultExecution timeMemory
232288pedy4000Ili (COI17_ili)C++14
49 / 100
4082 ms14584 KiB
#include <algorithm> #include <iostream> #include <bitset> #include <vector> using namespace std; const int N = 1e4 + 8; int n, m; string s; int type[N * 2]; bool mark[N * 2]; bitset <N> bt[N]; vector <int> in[N * 2], out[N * 2]; vector <int> one; void set0 (int d) { mark[d] = true; type[d] = 0; for (int v: in[d]) if (!mark[v]) set0(v); } int main() { ios::sync_with_stdio(false), cin.tie(0); cin >> n >> m >> s; for (int i = 0; i < m; i++) type[i] = (s[i] == '?'? 2: s[i] - '0'); for (int i = m; i < m + n; i++) type[i] = 2; for (int i = 0; i < m; i++) for (int j = 0; j < 2; j++) { char c; int ind; cin >> c >> ind; ind--; if (c == 'x') ind += m; in[i].push_back(ind); out[ind].push_back(i); } for (int i = 0; i < m + n; i++) if (type[i] == 0 && !mark[i]) set0(i); for (int i = 0; i < m + n; i++) mark[i] = 0; for (int i = 0; i < m; i++) { if (type[i] == 0) continue; for (int v: in[i]) { if (type[v] == 0) continue; if (m <= v) bt[i][v - m] = true; else bt[i] |= bt[v]; if (type[v] == 1) type[i] = 1; } if (bt[i].count() == 0) type[i] = 0; } for (int i = m - 1; ~i; i--) { if (type[i] != 1) continue; if (type[in[i][0]] == 1 || type[in[i][1]] == 1) continue; if (type[in[i][0]] == 2 && type[in[i][1]] == 2) { one.push_back(i); continue; } if (type[in[i][0]] == 0) type[in[i][1]] = 1; else type[in[i][0]] = 1; } for (int i = 0; i < m; i++) { if (type[i] != 2) continue; if (type[in[i][0]] == 1 || type[in[i][1]] == 1) { type[i] = 1; continue; } // if (type[in[i][0]] == 0 || type[in[i][1]] == 0) // continue; for (int v: one) if ((bt[i] & bt[v]) == bt[v]) { type[i] = 1; break; } } for (int i = 0; i < m; i++) cout << (type[i] == 2? '?': char('0' + type[i])); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...