Submission #209736

#	Time	Username	Problem	Language	Result	Execution time	Memory
209736		parsa_mobed	Ili (COI17_ili)	C++14	7 / 100	9 ms	3832 KiB

ili

#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 / 7
• Subtask 2: 0 / 42
• Subtask 3: 0 / 51