Submission #715946

#	Time	Username	Problem	Language	Result	Execution time	Memory
715946		Ahmed57	Ili (COI17_ili)	C++14	0 / 100	3 ms	4948 KiB

ili

#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];
    for(int i =1 ;i<=n;i++){
        v[i][i] = 1;
    }
    vector<int> ones;
    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{
            if(ze[i]){
                cout<<'0';
            }else{
                bool ss = 0;
                for(int j = 1;j<=n;j++){
                    if(v[i][j]&&on[j]){
                        ss = 1;
                        break;
                    }
                }
                if(ss){
                    cout<<'1';
                    ones.push_back(i);
                    continue;
                }
                for(auto j:ones){
                    if((v[j]&v[i]).count()==v[j].count()){
                        ss = 1;
                        break;
                    }
                }
                if(ss){
                    cout<<'1';
                    ones.push_back(i);
                    continue;
                }
                cout<<'?';
            }
        }
    }
}

Compilation message (stderr)

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++){
      |                   ~^~~~~~~~~

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