oj.uz

Submission #250816

# Submission time Handle Problem Language Result Execution time Memory
250816 2020-07-19T08:28:12 Z NONAME Ili (COI17_ili) C++14
100 / 100
 2892 ms 24400 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(2e4) + 500;

int n, m;
array <int, 2> a[N];
vector <int> g[N];
bool mk[N], m0[N], m1[N];
string s;
bitset <N> n1, vis[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[i] = 1;

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n + m; ++j)
            mk[j] = 0;

        if (s[i] != '?') {
            if (s[i] == '1') m1[i] = 1;
                else m0[i] = 1;
            continue;
        }

        dfs(i + n);
        for (int j = 1; j <= n; ++j)
            if (mk[j])
                vis[i][j] = 1;

        if ((vis[i] & n1).none()) m0[i] = 1;
            else m1[i] = 1;
    }

    for (int i = 1; i <= m; ++i) {
        if (s[i] == '?' && !m0[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[j] && !vis[i][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]) cout << "?"; else
        if (m0[i]) cout << "0";
            else cout << "1";
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 5 ms 1792 KB Output is correct
9 Correct 4 ms 1656 KB Output is correct
10 Correct 3 ms 1664 KB Output is correct
11 Correct 5 ms 1920 KB Output is correct
12 Correct 3 ms 1536 KB Output is correct
13 Correct 3 ms 1536 KB Output is correct
14 Correct 5 ms 1920 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 5 ms 1792 KB Output is correct
9 Correct 4 ms 1656 KB Output is correct
10 Correct 3 ms 1664 KB Output is correct
11 Correct 5 ms 1920 KB Output is correct
12 Correct 3 ms 1536 KB Output is correct
13 Correct 3 ms 1536 KB Output is correct
14 Correct 5 ms 1920 KB Output is correct
15 Correct 472 ms 13176 KB Output is correct
16 Correct 887 ms 17764 KB Output is correct
17 Correct 657 ms 17528 KB Output is correct
18 Correct 2546 ms 24400 KB Output is correct
19 Correct 696 ms 16760 KB Output is correct
20 Correct 2024 ms 22324 KB Output is correct
21 Correct 2892 ms 23812 KB Output is correct
22 Correct 779 ms 21680 KB Output is correct
23 Correct 807 ms 22960 KB Output is correct
24 Correct 781 ms 22708 KB Output is correct
25 Correct 619 ms 21300 KB Output is correct
26 Correct 629 ms 20984 KB Output is correct
27 Correct 609 ms 21240 KB Output is correct
28 Correct 557 ms 20344 KB Output is correct
29 Correct 589 ms 20600 KB Output is correct
30 Correct 571 ms 20728 KB Output is correct
31 Correct 428 ms 22520 KB Output is correct
32 Correct 577 ms 23416 KB Output is correct