Submission #40220

#	Time	Username	Problem	Language	Result	Execution time	Memory
40220		krauch	Ili (COI17_ili)	C++14	100 / 100	3290 ms	15528 KiB

ili

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;


#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

#define fname ""

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 1e4 + 6;

int n, m, a[N], l[N * 2], r[N * 2];
bool u[N * 2];
bitset < N > bit[N], bit1;
vector < int > vec, vec2, g[N * 2];

void dfs(int v) {
    if (u[v]) return;
    u[v] = 1;
    if (v > n) {
        dfs(l[v]);
        dfs(r[v]);
    }
}

void dfs2(int v) {
    u[v] = 1;
    for (auto to : g[v]) if (!u[to]) dfs2(to);
}

int main() {
	//ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

	#ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    scanf("%d %d\n", &n, &m);
    forn(i, 1, m) {
        char c;
        scanf("%c", &c);
        if (c == '?') a[i] = -1;
        else a[i] = c - '0';
    }
    scanf("\n");
    forn(i, 1, m) {
        char c;
        int x;
        scanf("%c%d ", &c, &x);
        if (c == 'x') {
            bit[i][x] = 1;
            l[i + n] = x;
            g[x].eb(i + n);
        }
        else {
            bit[i] |= bit[x];
            x += n;
            l[i + n] = x;
            g[x].eb(i + n);
        }
        scanf("%c%d\n", &c, &x);
        if (c == 'x') {
            bit[i][x] = 1;
            r[i + n] = x;
            g[x].eb(i + n);
        }
        else {
            bit[i] |= bit[x];
            x += n;
            r[i + n] = x;
            g[x].eb(i + n);
        }
        if (a[i] == 0) {
            dfs(i + n);
        }
        if (a[i] == 1) vec2.eb(i);
    }

    forn(i, 1, n) {
        if (!u[i]) {
            bit1[i] = 1;
            vec.eb(i);
        }
    }

    forn(i, 1, m) {
        if (a[i] == 0) continue;
        if (a[i] == 1) continue;
        if (!(bit1 & bit[i]).count()) {
            a[i] = 0;
            continue;
        }
        memset(u, 0, sizeof(u));
        for (auto it : vec) {
            if (!bit[i][it]) dfs2(it);
        }
        for (auto it : vec2) {
            if (!u[it + n]) {
                a[i] = 1;
                break;
            }
        }
    }

    forn(i, 1, m) {
        if (a[i] == -1) cout << "?";
        else cout << a[i];
    }
    cout << "\n";

	return 0;
}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:73:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n", &n, &m);
                             ^
ili.cpp:76:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c", &c);
                        ^
ili.cpp:80:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("\n");
                ^
ili.cpp:84:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c%d ", &c, &x);
                               ^
ili.cpp:96:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c%d\n", &c, &x);
                                ^

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