Submission #232871

#	Time	Username	Problem	Language	Result	Execution time	Memory
232871		shayan_p	Ili (COI17_ili)	C++14	100 / 100	1199 ms	13944 KiB

ili

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e4 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

bitset<maxn> bs[maxn], zr, tmp, dp;
vector<int> to1[maxn], to2[maxn];

int toInt(string s){
    stringstream ss;
    ss << s;
    int x;
    ss >> x;
    return x;
}
void inp(int i){
    string s;
    cin >> s;
    int id = toInt(s.substr(1))-1;
    if(s[0] == 'c')
	bs[i] = bs[i] | bs[id], to1[i].PB(id);
    else
	bs[i][id] = 1, to2[i].PB(id);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    for(int i = 0; i < m; i++){
	inp(i), inp(i);	
    }
    for(int i = 0; i < m; i++){
	if(s[i] == '0')
	    zr|= bs[i];
    }
    for(int i = 0; i < m; i++){
	tmp = zr & bs[i];
	if(tmp == bs[i])
	    s[i] = '0';
	bs[i] = bs[i] ^ tmp;
    }
    for(int i = 0; i < m; i++){
	if(s[i] == '?'){
	    tmp = zr | bs[i];
	    dp = 0;
	    bool bad = 0;
	    for(int j = 0; j < m; j++){
		for(int x : to1[j])
		    dp[j]= dp[j] || dp[x];
		for(int x : to2[j])
		    dp[j]= dp[j] || !tmp[x];
		bad|= (s[j] == '1' && dp[j] == 0);
	    }
	    if(bad)
		s[i] = '1';
	}
    }
    return cout << s << endl, 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51