oj.uz

Submission #516033

# Submission time Handle Problem Language Result Execution time Memory
516033 2022-01-20T10:16:24 Z Mahdi Ili (COI17_ili) C++17
0 / 100
 1 ms 848 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e4+5;
int n, m, l[N], r[N], a[N];
vector<int>g[N];
bitset<N>b[N];
string s;

void opr(const int &v){
    if(a[v]==0)
        a[l[v]]=a[r[v]]=0;
    b[l[v]]|=b[v];
    b[r[v]]|=b[v];
}

void dfs(const int &v){
    if(l[v]!=-1 && a[l[v]]==0 && a[r[v]]==0)
        a[v]=0;
    if(a[v]!=0){
        for(int u: g[v])
            b[u]&=b[v];
    }
    bitset<N>c;
    if(a[v]==1){
        for(int u=b[v]._Find_first();u<n+m;u=b[v]._Find_next(u))
            a[u]=1;
    }
}

int main(){
    //ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    cin>>s;
    fill(a, a+n, 2);
    for(int i=0;i<m;++i){
        if(s[i]=='1')
            a[i+n]=1;
        else if(s[i]=='?')
            a[i+n]=2;
    }
    memset(l, -1, 4*n);
    memset(r, -1, 4*n);
    for(int i=0;i<m;++i){
        string x;
        cin>>x;
        if(x[0]=='x')
            l[i+n]=x[1]-'1';
        else
            l[i+n]=n+x[1]-'1';
        cin>>x;
        if(x[0]=='x')
            r[i+n]=x[1]-'1';
        else
            r[i+n]=n+x[1]-'1';
        g[l[i+n]].push_back(i+n);
        g[r[i+n]].push_back(i+n);
    }
    for(int i=0;i<n+m;++i)
        b[i].set(i);
    for(int i=m+n-1;i>=n-1;--i)
        opr(i);
    for(int i=n;i<n+m;++i)
        b[i].set();
    for(int i=0;i<n+m;++i)
        dfs(i);
    for(int i=n;i<n+m;++i){
        if(a[i]!=2)
            cout<<a[i];
        else
            cout<<'?';
    }
    cout<<'\n';
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Incorrect 1 ms 848 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 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Incorrect 1 ms 848 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 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Incorrect 1 ms 848 KB Output isn't correct
4 Halted 0 ms 0 KB -