Submission #516135

#TimeUsernameProblemLanguageResultExecution timeMemory
516135MahdiIli (COI17_ili)C++17
100 / 100
256 ms43472 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 num(string x){ int a=0; for(int i=1;i<x.size();++i){ a*=10; a+=x[i]-'0'; } if(x[0]=='x') return a-1; return a+n-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; l[i+n]=num(x); cin>>x; r[i+n]=num(x); 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'; }

Compilation message (stderr)

ili.cpp: In function 'int num(std::string)':
ili.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=1;i<x.size();++i){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...