oj.uz

Submission #1081868

# Submission time Handle Problem Language Result Execution time Memory
1081868 2024-08-30T12:19:14 Z juicy Ili (COI17_ili) C++17
7 / 100
 1 ms 1372 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 10005;

int n, m;
int res[2 * N];
bitset<N> c[N];
vector<int> g[N];

void dfs(int u) {
  res[u] = 0;
  if (u <= m) {
    for (int v : g[u]) {
      if (res[v]) {
        res[v] = 0;
        dfs(v);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  string s; cin >> s; s = '&' + s;
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j < 2; ++j) {
      char c; int x; cin >> c >> x;
      x += c == 'x' ? m : 0;
      g[i].push_back(x);
    }
  }  
  memset(res, -1, sizeof(res));
  for (int i = 1; i <= m; ++i) {
    if (s[i] == '0') {
      dfs(i);
    } else if (s[i] == '1') {
      res[i] = 1;
    }
    for (int v : g[i]) {
      if (v <= m) {
        c[i] |= c[v];
      } else {
        c[i].set(v - m);
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (!res[g[i][0]] && !res[g[i][1]]) {
      res[i] = 0;
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (res[i] == -1) {
      res[i] = 0;
      bool flg = 0;
      for (int j = 1; j <= m; ++j) {
        if (res[j] == 1) {
          bool cant = 1;
          for (int v : g[j]) {
            if (v <= m) {
              cant &= !res[v];
            } else {
              cant &= !res[v] || c[i].test(v - m);
            }
          }
          if (cant) {
            flg = 1;
            break;
          }
        } 
      }
      res[i] = flg ? 1 : -1;
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (~res[i]) {
      cout << res[i];
    } else {
      cout << "?";
    }
  }
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 756 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 756 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Incorrect 1 ms 1372 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 756 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Incorrect 1 ms 1372 KB Output isn't correct
9 Halted 0 ms 0 KB -