Submission #545225

#	Time	Username	Problem	Language	Result	Execution time	Memory
545225		socpite	Ili (COI17_ili)	C++17	100 / 100	437 ms	25260 KiB

ili

#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;
int ans[maxn];

int main(){
    //freopen(".inp", "r", stdin);
    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 >> child[i][0].f;
        cin >> c;
        if(c == 'x')child[i][1].s = 0;
        else child[i][1].s = 1;
        cin >> child[i][1].f;
    }
    crr.set();
    for(int i = 1; i <= n; i++){
        subset[i][0].set();
        subset[i][0][i]=0;
        //for(int j = 1; j <= n; j++)cout << subset[i][0][j];
        //cout << endl;
    }
    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];
    }
    orval[0]=crr;
    //for(int i = 1; i <= n; i++)cout << crr[i];
    //cout << endl;
    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]){
                val[0] = crr&subset[i][1];
                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: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51