oj.uz

Submission #966581

# Submission time Handle Problem Language Result Execution time Memory
966581 2024-04-20T05:12:18 Z Cookie Ili (COI17_ili) C++14
100 / 100
 1666 ms 13912 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 19972207, pr = 31;
const int mxn = 2e4 + 5, mxq = 1e5 + 5, sq = 500, mxv = 10005;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!

int n, m;
bool vis[20005];
bitset<mxv>reach[10005], one;
bool can0[mxn + 1], can1[mxn + 1];
int lson[mxn + 1], rson[mxn + 1];
vt<int>adj[mxn + 1];
int id(string s){
    int num = 0;
    for(int i = 1; i < sz(s); i++){
        num = num * 10 + (s[i] - '0');
    }
    if(s[0] == 'x'){
        return(num);
    }
    else return(num + n);
}
void dfs(int s){
    vis[s] = 1;
    if(s > n){
        if(!vis[lson[s]])dfs(lson[s]);
        if(!vis[rson[s]])dfs(rson[s]);
    }
}
void dfsreach(int s, int root){
    if(s <= n)reach[root].set(s);
    else{
        dfsreach(lson[s], root);
        dfsreach(rson[s], root);
    }
}
void dfs2(int s){
    vis[s] = 1;
    for(auto i: adj[s]){
        if(!vis[i]){
            dfs2(i);
        }
    }
}
void solve(){
    cin >> n >> m;
    string s; cin >> s; s = '.' + s;
    for(int i = n + 1; i <= n + m; i++){
        string s1, s2; cin >> s1 >> s2;
        lson[i] = id(s1); rson[i] = id(s2);
        adj[lson[i]].pb(i); adj[rson[i]].pb(i);
    }
    for(int i = n + m; i >= n + 1; i--){
        if(!vis[i] && s[i - n] == '0'){
            dfs(i);
        }
        
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            one[i] = 1;
        }
    }
    for(int i = 1; i <= m; i++){
        
        dfsreach(i + n, i);
    }
    for(int i = 1; i <= m; i++){
        if((one & reach[i]).any()){
           
            can1[i] = 1; //can still be zero
        }
        else{
             can0[i] = 1; //certain is 0;
        }
    }
    for(int i = 1; i <= m; i++){
        if(s[i] != '?')cout << s[i];
        else if(can0[i] == 1){
            cout << 0;
        }else{
            memset(vis, 0, sizeof(vis));
            bool bad = 0;
            for(int j = 1; j <= n; j++){
                if(one[j] == 1 && !reach[i][j]){
                    dfs2(j);
                }
            }
            for(int j = 1; j <= m; j++){
                if(!vis[j + n] && s[j] == '1'){
                    bad = 1;
                    break;
                }
            }
            if(bad)cout << 1;
            else cout << '?';
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("i.inp", "r", stdin);
    //freopen("i.out", "w", stdout);
    int tt; tt = 1;
    while(tt--){
        solve();

    }
    return(0);
}

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2692 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 152 ms 9072 KB Output is correct
16 Correct 386 ms 11168 KB Output is correct
17 Correct 243 ms 13272 KB Output is correct
18 Correct 1573 ms 13688 KB Output is correct
19 Correct 295 ms 11096 KB Output is correct
20 Correct 1213 ms 13712 KB Output is correct
21 Correct 1666 ms 13912 KB Output is correct
22 Correct 234 ms 13492 KB Output is correct
23 Correct 244 ms 13748 KB Output is correct
24 Correct 233 ms 13740 KB Output is correct
25 Correct 208 ms 13404 KB Output is correct
26 Correct 205 ms 13404 KB Output is correct
27 Correct 213 ms 13400 KB Output is correct
28 Correct 165 ms 13256 KB Output is correct
29 Correct 191 ms 13300 KB Output is correct
30 Correct 170 ms 13148 KB Output is correct
31 Correct 179 ms 13652 KB Output is correct
32 Correct 244 ms 13908 KB Output is correct