Submission #250890

#	Time	Username	Problem	Language	Result	Execution time	Memory
250890		Vimmer	Ili (COI17_ili)	C++14	0 / 100	8 ms	13696 KiB

ili

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 100010
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <ll, 3> a3;
typedef array <ll, 4> a4;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


bool mk0[N], mk1[N], mk[N], mkr[N], found, mark[N];

set <int> se;

vector <int> g[N], vr[N];

vector <pair <int, int> > path[N];

string s1[N], s2[N];

int convert(string s)
{
    int t = 1, l = 0;

    for (int j = 1; j < sz(s); j++)
    {
        l += t * (s[j] - '0');

        t *= 10;
    }

    return l;
}

string c;

void dfs(int v, bool f)
{
    if (mk[v]) return;

    mk[v] = 1;

    for (auto i : (f ? vr[v] : g[v]))
    {
        bool f1 = 0, f2 = 0;

        int l = convert(s1[i]), r = convert(s2[i]);

        if (s1[i][0] == 'c') f1 = 1;
        if (s2[i][0] == 'c') f2 = 1;

        if (c[i] == '?')
        {
            if ((!f1 && mk1[l]) || (!f2 && mk1[r]) || (f1 && c[l - 1] == '1') || (f2 && c[r - 1] == '1')) {c[i] = '1'; dfs(i, 1);}
                else

             if (((!f1 && mk0[l]) || (f1 && c[l - 1] == '0')) && ((!f2 && mk0[r]) || (f2 && c[r - 1] == '0'))) {c[i] = '0'; dfs(i, 1);}

        }
        else
        {
            if ((!f1 && mk0[l]) || (f1 && c[l - 1] == '0'))
                {
                    if (f2) {c[r - 1] = '1'; dfs(r - 1, 1); continue;}

                    mk0[r] = 0;

                    mk1[r] = 1;

                    dfs(r, 0);
                }
                else if ((!f2 && mk0[r]) || (f2 && c[r - 1] == '0'))
                {
                    if (f1) {c[l - 1] = '1'; dfs(l - 1, 1); continue;}

                    mk0[l] = 0;

                    mk1[l] = 1;

                    dfs(l, 0);
                }
        }
    }
}

void go(int v)
{
    if (mark[v]) return;

    mark[v] = 1;

    if (found) return;

    for (auto it : path[v])
    {
        if (found) return;

        if (it.S == 0)
        {
            for (auto x : g[it.F])
            {
                if (found) return;

                if (se.find(x) != se.end()) {found = 1; return;}

                se.insert(x);
            }
        }
        else
        {
//            for (auto x : vr[it.F])
//            {
//                if (found) return;
//
//                if (se.find(x) != se.end()) {found = 1; return;}
//
//                se.insert(x);
//            }

//            go(it.F);
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin); freopen("output4.txt", "w", stdout);

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

    int n, m;

    cin >> n >> m;

    cin >> c;

    for (int i = 0; i < m; i++)
    {
        cin >> s1[i] >> s2[i];

        bool f1 = 0, f2 = 0;

        int l = convert(s1[i]), r = convert(s2[i]);

        if (s1[i][0] == 'c') f1 = 1;
        if (s2[i][0] == 'c') f2 = 1;

        path[i].pb({l, f1});
        path[i].pb({r, f2});

        int v1 = 0, v2 = 0;

        if (c[i] == '?')
        {
             if ((!f1 && mk1[l]) || (!f2 && mk1[r]) || (f1 && c[l - 1] == '1') || (f2 && c[r - 1] == '1')) c[i] = '1';
                else

             if (((!f1 && mk0[l]) || (f1 && c[l - 1] == '0')) && ((!f2 && mk0[r]) || (f2 && c[r - 1] == '0'))) c[i] = '0';
             else
             {
                 if (f1 || f2)
                 {
                    se.clear();

                    found = 0;

                    go(i);

                    if (found) c[i] = '1';
                 }

                if (f1) vr[l - 1].pb(i);
                  else g[l].pb(i);

                if (f2) vr[r - 1].pb(i);
                  else g[r].pb(i);
             }
        }
        else
        {
            if (c[i] == '0')
            {
                if (!f1)
                {
                    mk1[l] = 0;

                    mk0[l] = 1;

                    dfs(l, 0);
                } else {c[l - 1] = 0; dfs(l - 1, 1);}

                if (!f2)
                {
                    mk1[r] = 0;

                    mk0[r] = 1;

                    dfs(r, 0);
                } else {c[r - 1] = 0; dfs(r - 1, 1);}
            }
            else
            {
                if ((!f1 && mk0[l]) || (f1 && c[l - 1] == '0'))
                {
                    if (f2) {c[r - 1] = '1'; dfs(r - 1, 1); continue;}

                    mk0[r] = 0;

                    mk1[r] = 1;

                    dfs(r, 0);
                }
                else if ((!f2 && mk0[r]) || (f2 && c[r - 1] == '0'))
                {
                    if (f1) {c[l - 1] = '1'; dfs(l - 1, 1); continue;}

                    mk0[l] = 0;

                    mk1[l] = 1;

                    dfs(l, 0);
                }
                else
                {
                    if (f1) vr[l - 1].pb(i);
                      else g[l].pb(i);

                    if (f2)  vr[r - 1].pb(i);
                      else  g[r].pb(i);
                }
            }
        }
    }

    cout << c << endl;
}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:172:13: warning: unused variable 'v1' [-Wunused-variable]
         int v1 = 0, v2 = 0;
             ^~
ili.cpp:172:21: warning: unused variable 'v2' [-Wunused-variable]
         int v1 = 0, v2 = 0;
                     ^~

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