oj.uz

Submission #1087345

# Submission time Handle Problem Language Result Execution time Memory
1087345 2024-09-12T14:00:35 Z vysniak_grossmeister Ili (COI17_ili) C++17
49 / 100
 4000 ms 1628 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

const ll MAXN = 10505;

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

ll n, m;

map<ll,ll>mp;

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);

    }

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

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



            string curr = s;

            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';

            }

        }

    }

    cout << ans << "\n";

    return 0;

}

// //
// //

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 26 ms 860 KB Output is correct
9 Correct 21 ms 860 KB Output is correct
10 Correct 21 ms 860 KB Output is correct
11 Correct 29 ms 860 KB Output is correct
12 Correct 17 ms 856 KB Output is correct
13 Correct 16 ms 856 KB Output is correct
14 Correct 31 ms 860 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 26 ms 860 KB Output is correct
9 Correct 21 ms 860 KB Output is correct
10 Correct 21 ms 860 KB Output is correct
11 Correct 29 ms 860 KB Output is correct
12 Correct 17 ms 856 KB Output is correct
13 Correct 16 ms 856 KB Output is correct
14 Correct 31 ms 860 KB Output is correct
15 Execution timed out 4054 ms 1628 KB Time limit exceeded
16 Halted 0 ms 0 KB -