Submission #492597

#	Time	Username	Problem	Language	Result	Execution time	Memory
492597		radal	Ili (COI17_ili)	C++14	100 / 100	567 ms	2252 KiB

ili

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 2e4+20,mod = 1e9+7,inf = 1e18,sq = 400,sig = 26;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    return a+b;
}
vector<int> in[N],out[N];
int n,m;
string s;
bool fx[N];
int ans[N];
void rlx1(int v){
    if (fx[v]) return;
    ans[v] = 1;
    fx[v] = 1;
    for (int u : out[v]) rlx1(u);
    if (v > n){
        if (ans[in[v][0]] == 0) rlx1(in[v][1]);
        if (ans[in[v][1]] == 0) rlx1(in[v][0]);
    }
}
void rlx0(int v){
    if (fx[v]) return;
    fx[v] = 1;
    ans[v] = 0;
    for (int u : in[v]) rlx0(u);
    for (int u : out[v]){
        if (fx[u])
            continue;
        if (in[u][0] == v && fx[in[u][1]]) rlx0(u);
        else if (in[u][1] == v && fx[in[u][0]]) rlx0(u);
    }
}
bool rlx2(int v){
    if (ans[v] == 0) return 0;
    if (ans[v] == 1) return 1;
    ans[v] = 0;
    for (int u : in[v]){
        if (rlx2(u))
            return 1;
    }
    for (int u : out[v]){
        if (in[u][0] == v && ans[in[u][1]] == 0){
            if (rlx2(u)){
                return 1;
            }
        }
        else if (in[u][1] == v && ans[in[u][0]] == 0){
            if (rlx2(u)){
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(ans,-1,sizeof ans);
    cin >> n >> m >> s;
    rep(i,1,m+1){
        string x,y;
        cin >> x >> y;
        int u = 0,v = 0,g = x.size();
        rep(i,1,g){
            u *= 10;
            u += (x[i]-'0');
        }
        g = y.size();
        rep(i,1,g){
            v *= 10;
            v += (y[i]-'0');
        }
        if (x[0] == 'c') u += n;
        if (y[0] == 'c') v += n;
        in[i+n].pb(u);
        in[i+n].pb(v);
        out[u].pb(i+n);
        out[v].pb(i+n);
    }
    rep(i,0,m){
       if (s[i] == '0') rlx0(i+n+1);
        if (s[i] == '1'){
            rlx1(i+n+1);
        }
    }
    rep(i,1,n+1){
        if (ans[i] != -1) continue;
        if (rlx2(i)){
            ans[i] = 1;
            fx[i] = 1;
        }
        rep(i,1,n+m+1) if (!fx[i]) ans[i] = -1;
    }
    rep(i,0,m){
        if (ans[i+n+1] == 1) cout << 1;
        else if (ans[i+n+1] == 0) cout << 0;
        else{
            if (rlx2(i+n+1)){
                cout << 1;
                ans[1+n+i] = 1;
                fx[i+n+1] = 1;
            }
            else cout << '?';
            rep(i,1,n+1+m) if (!fx[i]) ans[i] = -1;
        }
    }
}

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