Submission #377871

#	Time	Username	Problem	Language	Result	Execution time	Memory
377871		Sara	Ili (COI17_ili)	C++14	100 / 100	677 ms	1772 KiB

ili

#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){
    tmp[v] = -1;
    if (v <= n) return;
    for (int u : adj[v]){
        dfs_set0(u);
    }
    return;
}
 
inline bool ok(int v){
 
    for (int i = 1; i <= n + m; i ++){
        tmp[i] = 1;
    }
 
    for (int i = 1; i <= n + m; i ++){
        if (ans[i] == -1){
            tmp[i] = -1;
        }
    }
 
    dfs_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);
 
        e[i] = {u, v};
 
    }
 
    for (int i = m; i >= 1; i --){
        int par = i + n;
        if (a[i] != '0') continue;
        ans[i + n] = -1;
        for (int u : adj[par]){
            if (n < u){
                a[u - n] = '0';
            }
            ans[u] = -1;
        }
    }

    for (int i = 1; i <= m; i ++){
        int par = i + n;
        int u = e[i].F;
        int v = e[i].S;
        if (ans[u] == -1 && ans[v] == -1){
            ans[par] = -1;
        }
    }

    for (int i = 1; i <= m; i ++){
        if ((ans[i + n] == 1) && (a[i] == '?')){
            a[i] = '0';
            ans[i + n] = 1 - ok(i + n);
            a[i] = '?';
        }
        if (ans[i + n] == 1) cout << 1;
        if (ans[i + n] == -1) cout << 0;
        if (ans[i + n] == 0) cout << '?';
    }
 
    return 0;
 
}

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51