oj.uz

Submission #516135

# Submission time Handle Problem Language Result Execution time Memory
516135 2022-01-20T12:30:57 Z Mahdi Ili (COI17_ili) C++17
100 / 100
 256 ms 43472 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 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

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){
      |                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 716 KB Output is correct
3 Correct 0 ms 844 KB Output is correct
4 Correct 1 ms 788 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 1 ms 848 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 716 KB Output is correct
3 Correct 0 ms 844 KB Output is correct
4 Correct 1 ms 788 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 2256 KB Output is correct
9 Correct 1 ms 1960 KB Output is correct
10 Correct 2 ms 2420 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 2 ms 2256 KB Output is correct
14 Correct 2 ms 2128 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 716 KB Output is correct
3 Correct 0 ms 844 KB Output is correct
4 Correct 1 ms 788 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 2256 KB Output is correct
9 Correct 1 ms 1960 KB Output is correct
10 Correct 2 ms 2420 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 2 ms 2256 KB Output is correct
14 Correct 2 ms 2128 KB Output is correct
15 Correct 24 ms 17440 KB Output is correct
16 Correct 26 ms 21908 KB Output is correct
17 Correct 26 ms 23552 KB Output is correct
18 Correct 32 ms 29568 KB Output is correct
19 Correct 24 ms 24436 KB Output is correct
20 Correct 34 ms 37492 KB Output is correct
21 Correct 37 ms 43472 KB Output is correct
22 Correct 208 ms 39688 KB Output is correct
23 Correct 256 ms 40664 KB Output is correct
24 Correct 247 ms 39992 KB Output is correct
25 Correct 203 ms 38928 KB Output is correct
26 Correct 205 ms 39484 KB Output is correct
27 Correct 196 ms 39356 KB Output is correct
28 Correct 176 ms 37424 KB Output is correct
29 Correct 200 ms 38692 KB Output is correct
30 Correct 180 ms 38864 KB Output is correct
31 Correct 181 ms 28212 KB Output is correct
32 Correct 169 ms 30692 KB Output is correct