oj.uz

Submission #145091

# Submission time Handle Problem Language Result Execution time Memory
145091 2019-08-18T18:17:41 Z Abelyan Ili (COI17_ili) C++17
100 / 100
 3338 ms 43640 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=2e4+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;
 
int g[N][2],ans[N];
bitset<N> has[N],zro;
vector<int> gn[N];
bool col[N];

int n,m;
int get(){
    char c;
    cin>>c;
    int k;
    cin>>k;
    //cout<<c<<" "<<k<<endl;
    if (c=='c')return n+k-1;
    return k-1;
}
 

int main(){
    fastio;
    srng;
    #ifdef ALEXPC
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    cin>>n>>m;
    //assert(n<=8);
    FOR(i,n){
        has[i][i]=1;
    }
    FORT(i,n,n+m-1){
        char c;
        cin>>c;
        ans[i]=2;
        if (c=='1')ans[i]=1;
        if (c=='0')ans[i]=0;
    }
    
    FORT(i,n,n+m-1){
        g[i][0]=get();
        g[i][1]=get();
        //cout<<g[i][0]<<" "<<g[i][1]<<endl;
        has[i]=has[g[i][0]]|has[g[i][1]];
        gn[g[i][0]].ad(i);
        gn[g[i][1]].ad(i);
        if (ans[i]==0)zro|=has[i];
    }
    FORT(i,n,n+m-1){
        if (ans[i]==2){
            if ((zro&has[i])==has[i]){
                ans[i]=0;
                continue;
            }
            FORT(j,0,n+m-1){
                col[j]=false;
            }
            queue<int> q;
            FOR(j,n){
                if (!zro[j] && !has[i][j]){
                    q.push(j);
                    col[j]=true;
                }
            }
            while(!q.empty()){
                int v=q.front();
                q.pop();
                trav(to,gn[v]){
                    if (!col[to]){
                        col[to]=true;
                        q.push(to);
                    }
                }
            }
            FORT(j,n,n+m-1){
                if (!col[j] && ans[j]==1){
                    ans[i]=1;
                    break;
                }
            }
        }
        
    }
    
    FORT(i,n,n+m-1){
        if (ans[i]!=2)cout<<(char)(ans[i]+'0');
        else cout<<'?';
    }
    
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 7 ms 2296 KB Output is correct
9 Correct 6 ms 2040 KB Output is correct
10 Correct 6 ms 2552 KB Output is correct
11 Correct 7 ms 2424 KB Output is correct
12 Correct 5 ms 2424 KB Output is correct
13 Correct 5 ms 2296 KB Output is correct
14 Correct 8 ms 2296 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 7 ms 2296 KB Output is correct
9 Correct 6 ms 2040 KB Output is correct
10 Correct 6 ms 2552 KB Output is correct
11 Correct 7 ms 2424 KB Output is correct
12 Correct 5 ms 2424 KB Output is correct
13 Correct 5 ms 2296 KB Output is correct
14 Correct 8 ms 2296 KB Output is correct
15 Correct 558 ms 17304 KB Output is correct
16 Correct 1181 ms 21992 KB Output is correct
17 Correct 909 ms 23672 KB Output is correct
18 Correct 3211 ms 29668 KB Output is correct
19 Correct 933 ms 24544 KB Output is correct
20 Correct 2477 ms 37524 KB Output is correct
21 Correct 3338 ms 43640 KB Output is correct
22 Correct 568 ms 39800 KB Output is correct
23 Correct 591 ms 40696 KB Output is correct
24 Correct 570 ms 40056 KB Output is correct
25 Correct 506 ms 38904 KB Output is correct
26 Correct 514 ms 39516 KB Output is correct
27 Correct 523 ms 39416 KB Output is correct
28 Correct 457 ms 37444 KB Output is correct
29 Correct 486 ms 38776 KB Output is correct
30 Correct 487 ms 38868 KB Output is correct
31 Correct 333 ms 28280 KB Output is correct
32 Correct 435 ms 30712 KB Output is correct