oj.uz

Submission #251483

# Submission time Handle Problem Language Result Execution time Memory
251483 2020-07-21T11:57:10 Z VEGAnn Ili (COI17_ili) C++14
100 / 100
 637 ms 2296 KB 
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
const int N = 20100;
vector<int> bck[N], to[N];
int n, m;
string s, t;
bool was[N];

void down(int v){
    s[v] = '0';

    for (int u : bck[v])
        down(u);
}

bool noone(int v){
    if (v >= m) return (s[v] - '0');

    int res = 0;

    for (int u : bck[v])
        res |= noone(u);

    return res;
}

void mark_all(int v){
    if (v >= m) t[v] = '0';

    for (int u : bck[v])
        mark_all(u);
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++){
        char t1, t2; int n1, n2;

        cin >> t1 >> n1 >> t2 >> n2;
        n1--; n2--;

        int fi = n1, se = n2;

        if (t1 == 'x') fi += m;
        if (t2 == 'x') se += m;

        bck[i].PB(fi);
        bck[i].PB(se);

        to[fi].PB(i);
        to[se].PB(i);
    }

    for (int i = 0; i < n; i++)
        s += "1";

    for (int i = 0; i < m; i++)
        if (s[i] == '0')
            down(i);

    for (int i = 0; i < m; i++){
        if (s[i] != '?') continue;

        if (!noone(i))
            s[i] = '0';
        else {
            t = s;

            mark_all(i);

            bool bad = 0;

            for (int i = 0; i < m; i++){
                was[i] = 0;

                for (int u : bck[i])
                    if (u < m)
                        was[i] |= was[u];
                    else was[i] |= (t[u] - '0');

                if (s[i] == '1' && !was[i]){
                    bad = 1;
                    break;
                }
            }

            if (bad)
                s[i] = '1';
        }
    }

    for (int i = 0; i < m; i++)
        cout << s[i];

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1408 KB Output is correct
2 Correct 1 ms 1280 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Correct 1 ms 1280 KB Output is correct
8 Correct 1 ms 1280 KB Output is correct
9 Correct 2 ms 1280 KB Output is correct
10 Correct 1 ms 1280 KB Output is correct
11 Correct 2 ms 1280 KB Output is correct
12 Correct 1 ms 1280 KB Output is correct
13 Correct 1 ms 1280 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1408 KB Output is correct
2 Correct 1 ms 1280 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Correct 1 ms 1280 KB Output is correct
8 Correct 1 ms 1280 KB Output is correct
9 Correct 2 ms 1280 KB Output is correct
10 Correct 1 ms 1280 KB Output is correct
11 Correct 2 ms 1280 KB Output is correct
12 Correct 1 ms 1280 KB Output is correct
13 Correct 1 ms 1280 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct
15 Correct 17 ms 1792 KB Output is correct
16 Correct 203 ms 1792 KB Output is correct
17 Correct 92 ms 1920 KB Output is correct
18 Correct 512 ms 2132 KB Output is correct
19 Correct 156 ms 1912 KB Output is correct
20 Correct 548 ms 2168 KB Output is correct
21 Correct 637 ms 2296 KB Output is correct
22 Correct 287 ms 2176 KB Output is correct
23 Correct 320 ms 2296 KB Output is correct
24 Correct 316 ms 2176 KB Output is correct
25 Correct 207 ms 1924 KB Output is correct
26 Correct 193 ms 2040 KB Output is correct
27 Correct 189 ms 1920 KB Output is correct
28 Correct 179 ms 1912 KB Output is correct
29 Correct 182 ms 1920 KB Output is correct
30 Correct 181 ms 1912 KB Output is correct
31 Correct 298 ms 1920 KB Output is correct
32 Correct 395 ms 2040 KB Output is correct