oj.uz

Submission #250805

# Submission time Handle Problem Language Result Execution time Memory
250805 2020-07-19T08:03:52 Z NONAME Ili (COI17_ili) C++14
0 / 100
 1 ms 1792 KB 
#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(1e4) + 500;

int n, m;
array <int, 2> a[2 * N];
vector <int> g[2 * N];
bool mk[N], m0[N], m1[N];
string s;
set <int> n1, vis[2 * 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);
        if (s[i] != '?') {
            if (s[i] == '0') m0[i] = 1;
                else m1[i] = 1;
            continue;
        }
        for (int j = 1; j <= n; ++j)
            if (mk[j]) {
                if (n1.count(j))
                    m1[i] = 1;
                vis[i].insert(j);
            }

        if (!m1[i])
            m0[i] = 0, 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 (int j = 1; j <= n; ++j)
                if (n1.count(j) && !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]) s[i] = '?'; else
        if (m0[i]) s[i] = '0';
            else s[i] = '1';
    }

    cout << s.substr(1);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1792 KB Output is correct
2 Incorrect 1 ms 1792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1792 KB Output is correct
2 Incorrect 1 ms 1792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1792 KB Output is correct
2 Incorrect 1 ms 1792 KB Output isn't correct
3 Halted 0 ms 0 KB -