oj.uz

Submission #377627

# Submission time Handle Problem Language Result Execution time Memory
377627 2021-03-14T13:38:56 Z Sara Ili (COI17_ili) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back

const int N = 10000 + 2;
const int LOG = 25;
const int MOD = 1e9 + 7;
const ll  inf = 1e9 + 5;

int n, m;
string a;
int ans[N];
int adj[N][2];
pair <int, int> e[N];
int help[N];
vector <int> zero;

void dfs_set0(int v){
    ans[v] = -1;
    for (int u : adj[v]){
        if (!ans[u]){
            dfs_set0(u);
        }
    }
    return;
}

void dfs(int v){
    help[v] = -1;
    for (int u : adj[v]){
        if (!help[u]){
            dfs(u);
        }
    }
    return;
}

bool ok(int v){
    for (int i = 1; i <= n + m; i ++){
        help[i] = 0;
    }
    for (int i : zero) dfs(i);
    dfs(v);
    for (int i = 1; i <= n; i ++){
        if (!help[i]){
            help[i] = 1;
        }
    }
    for (int i = 1; i <= m; i ++){
        if (help[e[i].F] == 1 || help[e[i].S] == 1){
            help[i + n] = 1;
        }
        if (help[e[i].F] == -1 && help[e[i].S] == -1){
            help[i + n] = -1;
        }
        if (a[i] == '1' && help[i + n] == -1) return 0;
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    cin >> n >> m >> a;
    a = ' ' + a;
    for (int i = 1; i <= m; i ++){
        char type;
        int u, v, par = i + n;
        cin >> type >> u;
        if (type == 'c') u += n;
        cin >> type >> v;
        if (type == 'c') v += n;
        adj[par][0] = u;
        adj[par][1] = v;
        if (a[i] == '0'){
            zero.pb(i + n);
            dfs_set0(par);
        }
        e[i] = {u, v};
    }
    for (int i = 1; i <= n + m; i ++){
        if (!ans[i]){
            ans[i] = 1;
        }
    }
    for (int i = 1; i <= m; i ++){
        if (ans[i + n] == 1){
            ans[i + n] = !ok(i + n);
        }
        if (ans[i + n] == 1) cout << 1;
        if (ans[i + n] == -1) cout << 0;
        if (ans[i + n] == 0) cout << '?';
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -