Submission #251483

#	Time	Username	Problem	Language	Result	Execution time	Memory
251483		VEGAnn	Ili (COI17_ili)	C++14	100 / 100	637 ms	2296 KiB

ili

#include <bits/stdc++.h>
#define PB push_back
using namespace std;
const int N = 20100;
vector<int> bck[N], to[N];
int n, m;
string s, t;
bool was[N];

void down(int v){
    s[v] = '0';

    for (int u : bck[v])
        down(u);
}

bool noone(int v){
    if (v >= m) return (s[v] - '0');

    int res = 0;

    for (int u : bck[v])
        res |= noone(u);

    return res;
}

void mark_all(int v){
    if (v >= m) t[v] = '0';

    for (int u : bck[v])
        mark_all(u);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++){
        char t1, t2; int n1, n2;

        cin >> t1 >> n1 >> t2 >> n2;
        n1--; n2--;

        int fi = n1, se = n2;

        if (t1 == 'x') fi += m;
        if (t2 == 'x') se += m;

        bck[i].PB(fi);
        bck[i].PB(se);

        to[fi].PB(i);
        to[se].PB(i);
    }

    for (int i = 0; i < n; i++)
        s += "1";

    for (int i = 0; i < m; i++)
        if (s[i] == '0')
            down(i);

    for (int i = 0; i < m; i++){
        if (s[i] != '?') continue;

        if (!noone(i))
            s[i] = '0';
        else {
            t = s;

            mark_all(i);

            bool bad = 0;

            for (int i = 0; i < m; i++){
                was[i] = 0;

                for (int u : bck[i])
                    if (u < m)
                        was[i] |= was[u];
                    else was[i] |= (t[u] - '0');

                if (s[i] == '1' && !was[i]){
                    bad = 1;
                    break;
                }
            }

            if (bad)
                s[i] = '1';
        }
    }

    for (int i = 0; i < m; i++)
        cout << s[i];

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51