oj.uz

Submission #715950

# Submission time Handle Problem Language Result Execution time Memory
715950 2023-03-28T14:50:05 Z Ahmed57 Ili (COI17_ili) C++14
0 / 100
 3 ms 4948 KB 
#include <bits/stdc++.h>

using namespace std;
vector<int> adj[200001];
int n,m;
int num(string s){
    int add = 0;
    if(s[0]=='c')add = n;
    long long ans = 0;
    for(int i = 1;i<s.size();i++){
        ans=ans*10+(s[i]-'0');
    }
    return ans+add;
}
signed main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    string s;cin>>s;
    for(int i = 1;i<=m;i++){
        string a1,a2;cin>>a1>>a2;
        adj[i+n].push_back(num(a1));
        adj[i+n].push_back(num(a2));
    }
    queue<int> q;
    int ze[n+m+5] = {0};
    int on[n+m+5] = {0};
    for(int i = 0;i<s.size();i++){
        if(s[i]=='0'){
            q.push(i+n+1);
            ze[i+n+1] = 1;
        }else if(s[i]=='1'){
            on[i+n+1] = 1;
        }
    }
    while(!q.empty()){
        int w = q.front();q.pop();
        for(auto j:adj[w]){
            if(!ze[j]){
                ze[j] = 1;
                q.push(j);
            }
        }
    }

    for(int i = n+1;i<=n+m;i++){
        if(s[i-n-1]=='1'){
            if(ze[adj[i][0]]){
                on[adj[i][1]] = 1;
            }if(ze[adj[i][1]]){
                on[adj[i][0]] = 1;
            }
        }if(s[i-n-1]=='?'){
            if(ze[adj[i][0]]&&ze[adj[i][1]])ze[i] = 1;
        }
    }
    bitset<20001> v[n+m+1];
    vector<int> ones;
    for(int i =1 ;i<=n;i++){
        v[i][i] = 1;
        if(on[i]){
            ones.push_back(i);
        }
    }
    for(int i = n+1;i<=n+m;i++){
        v[i] = (v[adj[i][0]]^v[adj[i][1]]);
        if(s[i-n-1]!='?'){
            if(s[i-n-1]=='1')ones.push_back(i);
            cout<<s[i-n-1];
        }
        else{
            bool o = 0,z = (ze[i]);
            for(auto j:ones){
                if((v[j]&v[i]).count()==v[j].count()){
                    o = 1;
                    break;
                }
            }
            o|=on[i];
            if(o&&z||(!o&&!z)){
                cout<<'?';
                continue;
            }
            if(z){
                cout<<'0';
            }
            if(o){
                cout<<'1';
                ones.push_back(i);
            }
        }
    }
}

Compilation message

ili.cpp: In function 'int num(std::string)':
ili.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i = 1;i<s.size();i++){
      |                   ~^~~~~~~~~
ili.cpp: In function 'int main()':
ili.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0;i<s.size();i++){
      |                   ~^~~~~~~~~
ili.cpp:79:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |             if(o&&z||(!o&&!z)){
      |                ~^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 3 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 3 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 3 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -