Submission #144959

#	Time	Username	Problem	Language	Result	Execution time	Memory
144959		Abelyan	Ili (COI17_ili)	C++17	0 / 100	2 ms	888 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 main(){
    fastio;
    srng;
    #ifdef ALEXPC
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    cin>>n>>m;
    FORT(i,0,n+m-1)ans[i]=2;
    FOR(i,n){
        has[i][i]=1;
    }
    FORT(i,n,n+m-1){
        char c;
        cin>>c;
        if (c=='1')ans[i]=1;
        if (c=='0')ans[i]=0;
    }
    
    FORT(i,n,n+m-1){
        string a,b;
        cin>>a>>b;
        if (a[0]=='c') g[i][0]=n+(a[1]-'1');
        else g[i][0]=(a[1]-'1');
        if (b[0]=='c') g[i][1]=n+(b[1]-'1');
        else g[i][1]=(b[1]-'1');
        //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: 0 / 7
• Subtask 2: 0 / 42
• Subtask 3: 0 / 51