oj.uz

Submission #377686

# Submission time Handle Problem Language Result Execution time Memory
377686 2021-03-14T18:48:49 Z Sara Ili (COI17_ili) C++14
0 / 100
 1 ms 876 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 = 20000 + 10;
const int LOG = 25;
const int MOD = 1e9 + 7;
const ll  inf = 1e9 + 5;
 
int n, m;
string a;
int ans[N];
int tmp[N];
int help[N];
vector <int> adj[N];
pair <int, int> e[N];
 
void dfs_set0(int v){
    ans[v] = -1;
    if (v <= n) return;
    for (int u : adj[v]){
        if (ans[u] == 1){
            dfs_set0(u);
        }
    }
    return;
}
 
void dfs2_set0(int v){
    tmp[v] = -1;
    if (v <= n) return;
    for (int u : adj[v]){
        dfs2_set0(u);
    }
    return;
}
 
inline bool ok(int v){
 
    for (int i = 1; i <= n + m; i ++){
        tmp[i] = ans[i];
    }

    dfs2_set0(v);
 
    for (int i = 1; i <= m; i ++){
 
        int par = i + n;
        int u = e[i].F;
        int v = e[i].S;
 
        if ((tmp[u] == 1) || (tmp[v] == 1)){
            tmp[par] = 1;
        }
        else {
            assert((tmp[u] == -1) && (tmp[v] == -1));
            tmp[par] = -1;
        }
 
        if ((tmp[par] == 1) && (a[i] == '0')) return 0;
        if ((tmp[par] == -1) && (a[i] == '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 <= n + m; i ++){
        ans[i] = 1;
    }

    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].pb(u); 
        adj[par].pb(v);

        if (a[i] == '0') dfs_set0(par);

        e[i] = {u, v};

    }

    for (int i = 1; i <= m; i ++){
        if ((ans[i + n] == 1) && (a[i] == '?')){
            ans[i + n] = 1 - 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 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Incorrect 1 ms 876 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 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Incorrect 1 ms 876 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 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Incorrect 1 ms 876 KB Output isn't correct
4 Halted 0 ms 0 KB -