oj.uz

Submission #545215

# Submission time Handle Problem Language Result Execution time Memory
545215 2022-04-04T03:22:06 Z socpite Ili (COI17_ili) C++17
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int maxn = 1e4+5;


pair<int, int> child[maxn][2];

int n, m;

string str;
bitset<maxn> subset[maxn][2];
bitset<maxn> val[2];
bitset<maxn> orval[2];
bitset<maxn> crr;
bitset<maxn> nw;

int ans[maxn];

int main(){
    cin >> n >> m >> str;
    for(int i = 1; i <= m; i++){
        char c;
        cin >> c;
        if(c == 'x')child[i][0].s = 0;
        else child[i][0].s = 1;
        cin >> c;
        child[i][0].f = c-'0';
        cin >> c;
        if(c == 'x')child[i][1].s = 0;
        else child[i][1].s = 1;
        cin >> c;
        child[i][1].f = c-'0';
    }
    crr.set();
    for(int i = 1; i <= n; i++){
        subset[i][0].set();
        subset[i][0][i]=0;
    }
    for(int i = 1; i <= m; i++){
        subset[i][1] = subset[child[i][1].f][child[i][1].s]&subset[child[i][0].f][child[i][0].s];
        //for(int j = 1; j <= n; j++)cout << subset[i][1][j];
        //cout << endl;
        if(str[i-1] == '0')crr&=subset[i][1];
    }
    for(int i = 1; i <= n; i++){
        orval[0][i]=crr[i];
    }
    for(int i = 1; i <= m; i++){
        orval[1][i] = orval[child[i][1].s][child[i][1].f]|orval[child[i][0].s][child[i][0].f];
    }
    for(int i = 1; i <= m; i++){
        if(str[i-1] =='?'){
            if(orval[1][i]){
                nw = crr&subset[i][1];
                for(int j = 1; j <= n; j++){
                    val[0][j]=nw[j];
                }
                bool gg = 0;
                for(int j = 1; j <= m; j++){
                    val[1][j] = val[child[j][1].s][child[j][1].f]|val[child[j][0].s][child[j][0].f];
                    if(str[j-1] != '?'){
                        //cout << val[1][j] << endl;
                        if(int(val[1][j]) != str[j-1]-'0')gg=1;
                    }
                }
                if(!gg)ans[i]=-1;
                else ans[i]=1;
            }
            else ans[i]=0;
        }
        else ans[i]=str[i-1]-'0';
        //cout << ans[i] << endl;
    }
    for(int i = 1; i <= m; i++){
        if(ans[i] == -1)cout << '?';
        else cout << ans[i];
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -