Submission #1081874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081874		juicy	Ili (COI17_ili)	C++17	100 / 100	487 ms	13504 KiB

ili

#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];
bool cant[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) {
      for (int j = 1; j <= m; ++j) {
        if (res[j]) {
          cant[j] = 1;
          for (int v : g[j]) {
            if (v <= m) {
              cant[j] &= !res[v] || cant[v];
            } else {
              cant[j] &= !res[v] || c[i].test(v - m);
            }
          }
          if (res[j] == 1 && cant[j]) {
            res[i] = 1;
            break;
          }
        } 
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (~res[i]) {
      cout << res[i];
    } else {
      cout << "?";
    }
  }
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51