oj.uz

Submission #145335

# Submission time Handle Problem Language Result Execution time Memory
145335 2019-08-19T15:53:12 Z SamAnd Ili (COI17_ili) C++17
100 / 100
 1092 ms 12828 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 10004;

int n, m;
bitset<N> a[N];
pair<pair<char, int>, pair<char, int> > g[N];

char anss[N], ans[N];

bitset<N> x0;

int main()
{
    cin >> n >> m;
    cin >> anss;
    for (int i = 1; i <= m; ++i)
        ans[i] = anss[i - 1];
    for (int i = 1; i <= m; ++i)
    {
        char s1, s2;
        int x1, x2;
        cin >> s1 >> x1 >> s2 >> x2;
        if (s1 == 'c')
            a[i] = a[x1];
        else
            a[i][x1] = 1;
        if (s2 == 'c')
            a[i] = (a[i] | a[x2]);
        else
            a[i][x2] = 1;
        g[i] = m_p(m_p(s1, x1), m_p(s2, x2));
    }
    for (int i = 1; i <= m; ++i)
    {
        if (ans[i] == '0')
        {
            x0 = (x0 | a[i]);
        }
    }
    for (int i = 1; i <= m; ++i)
    {
        if ((a[i] & x0) == a[i])
            ans[i] = '0';
    }
    for (int i = 1; i <= m; ++i)
    {
        bitset<N> z = (a[i] | x0);
        for (int j = 1; j <= m; ++j)
        {
            bool z1 = false, z2 = false;
            if (g[j].first.first == 'x')
            {
                if (z[g[j].first.second] == 1)
                    z1 = true;
            }
            else
            {
                if (anss[g[j].first.second] == '0')
                    z1 = true;
            }
            if (g[j].second.first == 'x')
            {
                if (z[g[j].second.second] == 1)
                    z2 = true;
            }
            else
            {
                if (anss[g[j].second.second] == '0')
                    z2 = true;
            }
            if (z1 && z2)
                anss[j] = '0';
            else
                anss[j] = ans[j];
            if (ans[j] == '1' && anss[j] == '0')
            {
                ans[i] = '1';
                break;
            }
        }
    }
    for (int i = 1; i <= m; ++i)
        cout << ans[i];
    cout << endl;
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 888 KB Output is correct
9 Correct 4 ms 764 KB Output is correct
10 Correct 4 ms 888 KB Output is correct
11 Correct 4 ms 888 KB Output is correct
12 Correct 4 ms 888 KB Output is correct
13 Correct 4 ms 888 KB Output is correct
14 Correct 4 ms 888 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 888 KB Output is correct
9 Correct 4 ms 764 KB Output is correct
10 Correct 4 ms 888 KB Output is correct
11 Correct 4 ms 888 KB Output is correct
12 Correct 4 ms 888 KB Output is correct
13 Correct 4 ms 888 KB Output is correct
14 Correct 4 ms 888 KB Output is correct
15 Correct 78 ms 7884 KB Output is correct
16 Correct 359 ms 9080 KB Output is correct
17 Correct 470 ms 10972 KB Output is correct
18 Correct 506 ms 12664 KB Output is correct
19 Correct 371 ms 9336 KB Output is correct
20 Correct 1092 ms 12664 KB Output is correct
21 Correct 753 ms 12824 KB Output is correct
22 Correct 99 ms 12280 KB Output is correct
23 Correct 102 ms 12740 KB Output is correct
24 Correct 98 ms 12664 KB Output is correct
25 Correct 226 ms 12672 KB Output is correct
26 Correct 228 ms 12536 KB Output is correct
27 Correct 224 ms 12584 KB Output is correct
28 Correct 219 ms 12280 KB Output is correct
29 Correct 218 ms 12536 KB Output is correct
30 Correct 221 ms 12480 KB Output is correct
31 Correct 191 ms 12828 KB Output is correct
32 Correct 221 ms 12828 KB Output is correct