oj.uz

Submission #209736

# Submission time Handle Problem Language Result Execution time Memory
209736 2020-03-15T12:56:13 Z parsa_mobed Ili (COI17_ili) C++14
7 / 100
 9 ms 3832 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 2e4 + 5;
int a[N], lp[N], rp[N];
vector <int> Out[N];
bitset <N> reach[N], good[N], tmp, bt;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    memset(a, -1, sizeof a);
    for (int i = 1; i <= m; i++) {
        char c; cin >> c;
        if (c == '1') a[i + n] = 1;
        if (c == '0') a[i + n] = 0;
    }
    for (int i = 1; i <= m; i++) {
        char c1, c2; int v1, v2; cin >> c1 >> v1 >> c2 >> v2;
        if (c1 == 'x') Out[v1].push_back(i + n), lp[i + n] = v1;
        else Out[v1 + n].push_back(i + n), lp[i + n] = v1 + n;
        if (c2 == 'x') Out[v2].push_back(i + n), rp[i + n] = v2;
        else Out[v2 + n].push_back(i + n), rp[i + n] = v2 + n;
    }
    for (int i = n + m; i >= 1; i--) {
        reach[i][i] = 1;
        for (int u : Out[i]) {
            reach[i] |= reach[u];
            if (a[u] == 0) a[i] = 0;
        }
    }
    for (int i = 1; i <= n + m; i++) {
        if (a[lp[i]] == 0 && a[rp[i]] == 0) a[i] = 0;
        if (a[i] == 0) bt[i] = 1;
    }
    for (int i = 1; i <= n + m; i++) if (a[i] == 1) good[lp[i]][rp[i]] = good[rp[i]][lp[i]] = 1;
    for (int i = 1; i <= n + m; i++) for (int j = 1; j <= n + m; j++) {
        good[i][j] = good[i][j] | good[lp[i]][j] | good[rp[i]][j] | good[i][lp[j]] | good[i][rp[j]];
    }
    for (int i = 1; i <= n + m; i++) {
        if (a[lp[i]] == 1 || a[rp[i]] == 1 || good[lp[i]][rp[i]] == 1 || good[i][i] == 1) a[i] = 1;
        tmp = good[i] & bt;
        if (tmp.count() > 0) a[i] = 1;
    }
    for (int i = n + 1; i <= n + m; i++) {
        if (a[i] == -1) cout << '?';
        else cout << a[i];
    }
    cout << "\n";

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 42.0

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

Subtask #3
0 / 51.0

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