oj.uz

답안 #753099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753099 2023-06-04T14:49:43 Z Username4132 Ili (COI17_ili) C++14
100 / 100
 68 ms 47232 KB 
#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
 
const int MAXN=10070;
int n, m, pr[MAXN][2];
bool pb[MAXN][2];
string info, ans;
bitset<MAXN> arr[MAXN], wi[MAXN], wo[MAXN], brr[MAXN], one("1"), zero("0"), nuli, uni, add;
vector<int> upb[MAXN], upt[MAXN];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> info;
    ans.assign(m, '?');
    forn(i, m){
        char c1, c2;
        int a1, a2;
        cin >> c1 >> a1 >> c2 >> a2;
        --a1, --a2;
        bitset<MAXN> bi1 = c1=='x'? (one<<a1) : arr[a1];
        bitset<MAXN> bi2 = c2=='x'? (one<<a2) : arr[a2];
        arr[i]=bi1|bi2;
        pb[i][0]=(c1=='x'), pb[i][1]=(c2=='x');
        pr[i][0]=a1, pr[i][1]=a2;
        ((c1=='x')? upb : upt)[a1].PB(i);
        ((c2=='x')? upb : upt)[a2].PB(i);
    }
    forn(i, m) if(info[i]=='0') nuli|=arr[i];
    nuli=~nuli;
    forn(i, m) if(info[i]=='1') uni|=(1<<i);
    forn(i, m){
        arr[i]&=nuli;
        if(arr[i].count()==0) ans[i]='0';
    }
    dforn(i, m){
        wo[i]|=(one<<i);
        for(int to:upt[i]) wo[i]|=wo[to];
    }
    forn(i, n) for(int to:upb[i]) wi[i]|=wo[to];
    forn(i, n) if((nuli&(one<<i)).count()==0) wi[i]=~zero;
    forn(i, m){
        bitset<MAXN> b1 = pb[i][0]? wi[pr[i][0]] : brr[pr[i][0]];
        bitset<MAXN> b2 = pb[i][1]? wi[pr[i][1]] : brr[pr[i][1]];
        brr[i]=b1&b2;
    }
    forn(i, m) if(info[i]=='1') add|=brr[i];
    forn(i, m) if((add&(one<<i)).count()) ans[i]='1';
    cout << ans << endl;    
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2388 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 4 ms 2804 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 3 ms 2644 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2388 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 4 ms 2804 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 3 ms 2644 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 38 ms 23968 KB Output is correct
16 Correct 44 ms 28856 KB Output is correct
17 Correct 59 ms 33280 KB Output is correct
18 Correct 61 ms 40044 KB Output is correct
19 Correct 44 ms 30436 KB Output is correct
20 Correct 58 ms 43892 KB Output is correct
21 Correct 68 ms 47232 KB Output is correct
22 Correct 56 ms 44228 KB Output is correct
23 Correct 52 ms 45688 KB Output is correct
24 Correct 53 ms 45268 KB Output is correct
25 Correct 62 ms 37876 KB Output is correct
26 Correct 54 ms 37500 KB Output is correct
27 Correct 57 ms 37584 KB Output is correct
28 Correct 58 ms 36712 KB Output is correct
29 Correct 52 ms 37112 KB Output is correct
30 Correct 55 ms 37352 KB Output is correct
31 Correct 49 ms 39596 KB Output is correct
32 Correct 52 ms 40740 KB Output is correct