Submission #56413

#TimeUsernameProblemLanguageResultExecution timeMemory
56413polyfishIli (COI17_ili)C++14
49 / 100
7 ms1700 KiB
//I love armpit fetish #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "data" const int MAX_N = 10002; const int BITSET_SIZE = 501; ///notice const int INF = 1e9; int m, n, outcome[MAX_N], curVal[MAX_N], val[MAX_N], f[MAX_N]; vector<int> input[MAX_N]; bitset<BITSET_SIZE> subset[MAX_N]; string element_state; void enter() { cin >> n >> m >> element_state; for (int i=1; i<=m; ++i) { char x1, x2; int L, R; cin >> x1 >> L >> x2 >> R; if (x1=='x') { subset[i].set(L); input[i].push_back(-L); } else { input[i].push_back(L); } if (x2=='x') { subset[i].set(R); input[i].push_back(-R); } else { input[i].push_back(R); } } } void visit(int u) { for (int i=0; i<input[u].size(); ++i) { int v = input[u][i]; if (v>0) { outcome[v] = u; visit(v); subset[u] |= subset[v]; } } } void find_0s_element() { bitset<BITSET_SIZE> s; for (int i=1; i<=m; ++i) if (element_state[i-1]=='0') s |= subset[i]; memset(curVal, -1, sizeof(curVal)); for (int i=1; i<=n; ++i) if (s.test(i)) curVal[i] = 0; for (int i=1; i<=m; ++i) if ((s | subset[i]) == s) element_state[i-1] = '0'; } int check(int u) { if (f[u]!=INF) return f[u]; f[u] = 0; for (int i=0; i<input[u].size(); ++i) { int v = input[u][i]; if (v<0) { f[u] |= val[-v]; } else { int tmp = check(v); if (tmp==-1) return f[u] = -1; f[u] |= tmp; } } if (element_state[u-1]!='?' && element_state[u-1]-'0' != f[u]) return f[u] = -1; return f[u]; } void solve() { memset(outcome, -1, sizeof(outcome)); for (int i=1; i<=m; ++i) if (outcome[i]==-1) visit(i); find_0s_element(); for (int i=1; i<=m; ++i) { if (element_state[i-1] == '?') { for (int j=1; j<=n; ++j) { val[j] = curVal[j]; if (subset[i].test(j)) val[j] = 0; if (val[j]==-1) val[j] = 1; } //PR(val, n); bool ok = true; for (int i=1; i<=m; ++i) f[i] = INF; for (int i=1; i<=m; ++i) { if (check(i)==-1) { ok = false; break; } } //PR(f, m); if (!ok) element_state[i-1] = '1'; } } cout << element_state; } int main() { //#define OFFLINE_JUDGE doraemon #ifdef OFFLINE_JUDGE freopen(FILE_NAME".inp", "r", stdin); freopen(FILE_NAME".out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); enter(); solve(); }

Compilation message (stderr)

ili.cpp: In function 'void visit(int)':
ili.cpp:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<input[u].size(); ++i) {
                ~^~~~~~~~~~~~~~~~
ili.cpp: In function 'int check(int)':
ili.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<input[u].size(); ++i) {
                ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...