Submission #516033

#TimeUsernameProblemLanguageResultExecution timeMemory
516033MahdiIli (COI17_ili)C++17
0 / 100
1 ms848 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...