oj.uz

Submission #377633

# Submission time Handle Problem Language Result Execution time Memory
377633 2021-03-14T14:07:48 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;
    for (int u : adj[v]){
        if (ans[u] == 0){
            dfs_set0(u);
        }
    }
    return;
}

void dfs2_set0(int v){
    tmp[v] = -1;
    for (int u : adj[v]){
        if (tmp[u] == 0){
            dfs2_set0(u);
        }
    }
    return;
}

inline bool ok(int v){

    for (int i = 1; i <= n + m; i ++){
        tmp[i] = 0;
    }

    dfs2_set0(v);

    for (int i = 1; i <= n; i ++){
        if (tmp[i] == 0){
            tmp[i] = help[i];
        }
    }

    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 {
            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 <= 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 <= n + m; i ++){
        if (ans[i] == 0){
            ans[i] = 1;
        }
        help[i] = ans[i];
    }
    for (int i = 1; i <= m; i ++){
        if (ans[i + n] == 1){
            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 -