Submission #145091

#	Time	Username	Problem	Language	Result	Execution time	Memory
145091		Abelyan	Ili (COI17_ili)	C++17	100 / 100	3338 ms	43640 KiB

ili

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=2e4+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;
 
int g[N][2],ans[N];
bitset<N> has[N],zro;
vector<int> gn[N];
bool col[N];

int n,m;
int get(){
    char c;
    cin>>c;
    int k;
    cin>>k;
    //cout<<c<<" "<<k<<endl;
    if (c=='c')return n+k-1;
    return k-1;
}
 

int main(){
    fastio;
    srng;
    #ifdef ALEXPC
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    cin>>n>>m;
    //assert(n<=8);
    FOR(i,n){
        has[i][i]=1;
    }
    FORT(i,n,n+m-1){
        char c;
        cin>>c;
        ans[i]=2;
        if (c=='1')ans[i]=1;
        if (c=='0')ans[i]=0;
    }
    
    FORT(i,n,n+m-1){
        g[i][0]=get();
        g[i][1]=get();
        //cout<<g[i][0]<<" "<<g[i][1]<<endl;
        has[i]=has[g[i][0]]|has[g[i][1]];
        gn[g[i][0]].ad(i);
        gn[g[i][1]].ad(i);
        if (ans[i]==0)zro|=has[i];
    }
    FORT(i,n,n+m-1){
        if (ans[i]==2){
            if ((zro&has[i])==has[i]){
                ans[i]=0;
                continue;
            }
            FORT(j,0,n+m-1){
                col[j]=false;
            }
            queue<int> q;
            FOR(j,n){
                if (!zro[j] && !has[i][j]){
                    q.push(j);
                    col[j]=true;
                }
            }
            while(!q.empty()){
                int v=q.front();
                q.pop();
                trav(to,gn[v]){
                    if (!col[to]){
                        col[to]=true;
                        q.push(to);
                    }
                }
            }
            FORT(j,n,n+m-1){
                if (!col[j] && ans[j]==1){
                    ans[i]=1;
                    break;
                }
            }
        }
        
    }
    
    FORT(i,n,n+m-1){
        if (ans[i]!=2)cout<<(char)(ans[i]+'0');
        else cout<<'?';
    }
    
    return 0;
}

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