Submission #1087348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087348		vysniak_grossmeister	Ili (COI17_ili)	C++17	100 / 100	3863 ms	6104 KiB

ili

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
using namespace std;
typedef int ll;

const ll mod = 1e9 + 7;

const ll MAXN = 100505;

vector<ll>in[MAXN];
vector<ll>out[MAXN];

ll n, m;

ll mp[MAXN];

void push_one(ll x)
{

    if(mp[x] == 0 or mp[x] == 1) return;

    mp[x] = 1;

    for(auto to : out[x])
    {

        push_one(to);

    }

}

void push_zero(ll x)
{

    if(mp[x] == 0) return;

    mp[x] = 0;

    if(x >= n + 1)
    {

        for(auto to : in[x])
        {

            push_zero(to);

        }

    }

}

bool checker(string S)
{

    for(ll i = 1; i <= n + m; ++i)
    {

        mp[i] = -1ll;;

    }
    ll sum = 0;
    for(ll i = 1; i <= m; ++i)
    {

        if(S[i - 1] == '0')
        {

            push_zero(i + n);

            sum += i + n;

        }

    }



    for(ll i = 1; i <= n; ++i)
    {

        push_one(i);

    }

    bool ret = true;

    for(ll i = 1; i <= m; ++i)
    {



        ll v = i + n;

        bool valid1 = true;
        bool valid2 = true;

        if(S[i - 1] == '0' and mp[v] != 0)
        {

            valid1 = (false);

        }
        if(S[i - 1] == '1' and mp[v] != 1)
        {

            valid2 = (false);

        }

        if(!valid1 or !valid2) ret = false;

    }



    if(!ret) return false;
    else return true;

}

int main()
{

   // ifstream cin("mooyomooyo.in");
   // ofstream cout("mooyomooyo.out");

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


    cin >> n >> m;

    string s;
    cin >> s;

    string ans = s;

    for(ll i = 1; i <= m; ++i)
    {

        string s1, s2;
        cin >> s1 >> s2;

        ll v1 = 0;
        ll v2 = 0;

        ll base = 1;

        for(ll j = s1.size() - 1; j >= 1; --j)
        {

            v1 += int(s1[j] - '0') * base;

            base *= 10;

        }

        base = 1;

        for(ll j = s2.size() - 1; j >= 1; --j)
        {

            v2 += int(s2[j] - '0') * base;

            base *= 10;

        }

        if(s1[0] == 'c') v1 += n;
        if(s2[0] == 'c') v2 += n;

        ll V = i + n;



        in[V].push_back(v1);
        in[V].push_back(v2);

        out[v1].push_back(V);
        out[v2].push_back(V);

    }
    string curr = s;
    for(ll i = 1; i <= m; ++i)
    {

        if(s[i - 1] == '?')
        {





            bool can1 = false;
            bool can2 = false;

            // case 0

            curr[i - 1] = '0';

            if(checker(curr) == true) can1 = !(can1);

            // case 1

            curr[i - 1] = '1';

            if(checker(curr) == true) can2 = !(can2);



            if(can1 == can2)
            {

                ans[i - 1] = '?';

            }
            else if(can1)
            {

                ans[i - 1] = '0';

            }
            else if(can2)
            {

                ans[i - 1] = '1';

            }

            curr[i - 1] = s[i - 1];

        }

    }

    cout << ans << "\n";

    return 0;

}

// //
// //

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