답안 #40220 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40220	2018-01-30T06:19:16 Z	krauch	Ili (COI17_ili)	C++14	100 / 100	3290 ms	15528 KB

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

*/
#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

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.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14976 KB	Output is correct
2	Correct	1 ms	14976 KB	Output is correct
3	Correct	1 ms	14976 KB	Output is correct
4	Correct	0 ms	14976 KB	Output is correct
5	Correct	0 ms	14976 KB	Output is correct
6	Correct	0 ms	14976 KB	Output is correct
7	Correct	0 ms	14976 KB	Output is correct

Subtask #2
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14976 KB	Output is correct
2	Correct	1 ms	14976 KB	Output is correct
3	Correct	1 ms	14976 KB	Output is correct
4	Correct	0 ms	14976 KB	Output is correct
5	Correct	0 ms	14976 KB	Output is correct
6	Correct	0 ms	14976 KB	Output is correct
7	Correct	0 ms	14976 KB	Output is correct
8	Correct	3 ms	14976 KB	Output is correct
9	Correct	2 ms	14976 KB	Output is correct
10	Correct	2 ms	14976 KB	Output is correct
11	Correct	3 ms	14976 KB	Output is correct
12	Correct	2 ms	14976 KB	Output is correct
13	Correct	2 ms	14976 KB	Output is correct
14	Correct	4 ms	14976 KB	Output is correct

Subtask #3
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14976 KB	Output is correct
2	Correct	1 ms	14976 KB	Output is correct
3	Correct	1 ms	14976 KB	Output is correct
4	Correct	0 ms	14976 KB	Output is correct
5	Correct	0 ms	14976 KB	Output is correct
6	Correct	0 ms	14976 KB	Output is correct
7	Correct	0 ms	14976 KB	Output is correct
8	Correct	3 ms	14976 KB	Output is correct
9	Correct	2 ms	14976 KB	Output is correct
10	Correct	2 ms	14976 KB	Output is correct
11	Correct	3 ms	14976 KB	Output is correct
12	Correct	2 ms	14976 KB	Output is correct
13	Correct	2 ms	14976 KB	Output is correct
14	Correct	4 ms	14976 KB	Output is correct
15	Correct	491 ms	15108 KB	Output is correct
16	Correct	1049 ms	15240 KB	Output is correct
17	Correct	760 ms	15240 KB	Output is correct
18	Correct	3290 ms	15240 KB	Output is correct
19	Correct	739 ms	15240 KB	Output is correct
20	Correct	2060 ms	15376 KB	Output is correct
21	Correct	3036 ms	15372 KB	Output is correct
22	Correct	374 ms	15528 KB	Output is correct
23	Correct	378 ms	15524 KB	Output is correct
24	Correct	402 ms	15512 KB	Output is correct
25	Correct	290 ms	15260 KB	Output is correct
26	Correct	309 ms	15260 KB	Output is correct
27	Correct	298 ms	15260 KB	Output is correct
28	Correct	252 ms	15260 KB	Output is correct
29	Correct	268 ms	15260 KB	Output is correct
30	Correct	274 ms	15260 KB	Output is correct
31	Correct	184 ms	15276 KB	Output is correct
32	Correct	270 ms	15260 KB	Output is correct

답안 #40220

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 42.0 / 42.0

Subtask #3 51.0 / 51.0

Subtask #1
7.0 / 7.0

Subtask #2
42.0 / 42.0

Subtask #3
51.0 / 51.0