Submission #753099

#	Time	Username	Problem	Language	Result	Execution time	Memory
753099		Username4132	Ili (COI17_ili)	C++14	100 / 100	68 ms	47232 KiB

ili

#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 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51