oj.uz

Submission #715961

# Submission time Handle Problem Language Result Execution time Memory
715961 2023-03-28T15:32:20 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;
    int aa1[m+1],aa2[m+1];
    for(int i = 1;i<=m;i++){
        string a1,a2;cin>>a1>>a2;
        aa1[i] = num(a1);
        aa2[i] = num(a2);
        adj[i+n].push_back(num(a1));
        adj[i+n].push_back(num(a2));
    }
    queue<int> q;
    vector<int> ze(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;
        }
    }
    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(ze[i]){
            cout<<'0';
            continue;
        }
        vector<int> upd = ze;
        upd[i] = 1;
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            int w = q.front();q.pop();
            for(auto j:adj[w]){
                upd[j] = 1;
                q.push(j);
            }
        }
        bool ss = 1;
        for(int j = n+1;j<=n+m;j++){
            upd[j] = !(!upd[adj[j][0]]||!upd[adj[j][1]]);
            if(s[j-n-1]!='?'){
                if(s[j-n-1]=='1'&&upd[j]){
                    ss = 0;
                    break;
                }if(s[j-n-1]=='0'&&!upd[j]){
                    ss = 0;
                    break;
                }
            }
        }
        if(ss){
            cout<<'?';
        }else{
            cout<<'1';
        }
    }
}

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:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0;i<s.size();i++){
      |                   ~^~~~~~~~~
ili.cpp:19:9: warning: variable 'aa1' set but not used [-Wunused-but-set-variable]
   19 |     int aa1[m+1],aa2[m+1];
      |         ^~~
ili.cpp:19:18: warning: variable 'aa2' set but not used [-Wunused-but-set-variable]
   19 |     int aa1[m+1],aa2[m+1];
      |                  ^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 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 2 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 2 ms 4948 KB Output is correct
3 Incorrect 3 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -