Submission #419487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
419487	2021-06-07T07:44:37 Z	Ronin13	Ili (COI17_ili)	C++14	0 / 100	31 ms	47300 KB

ili

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define epb emplace_back
#define pb push_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

int n,m;
int conv(string x){
    string t="";
    for(int i=1;i<x.size();i++){
        t+=x[i];
    }
    int f=stoi(t);
    if(x[0]=='x')return f;
    return f+n;
}

vector<vector<int> >g(2000001);

void solve(){
    cin>>n>>m;
    string s;cin>>s;
    pii a[n+1+m];
    for(int i=1;i<=m;i++){
        string s,b;cin>>s>>b;
        int x=conv(s),y=conv(b);
        g[x].pb(i+n);
        g[y].pb(i+n);
        a[i+n].f=x,a[i+n].s=y;
    }
    vector<bool>used(200001,false);
    queue<int>q;
    queue<int>q1;
    vector<bool>used1(200001,false);
    for(int i=0;i<m;i++){
        if(s[i]=='0'){
            q.push(i+1+n);
            used[i+1+n]=true;
        }
    }
    while(!q.empty()){
        int v=q.front();
        q.pop();
        if(v>n){
            q.push(a[v].f),q.push(a[v].s);
            used[a[v].f]=used[a[v].s]=true;
        }
        for(int to:g[v]){
            if(s[to-1]=='0'){
                if(!used[a[to].f])q.push(a[to].f),used[a[to].f]=true;
                if(!used[a[to].f])q.push(a[to].s),used[a[to].s]=true;
            }
            if(s[to-1]=='1'){
                if(!used[a[to].f])q1.push(a[to].f),used1[a[to].f]=true;
                if(!used[a[to].s])q1.push(a[to].s),used1[a[to].s]=true;
            }
            if(s[to-1]=='?'){
                if(used[a[to].f]&&used[a[to].s])q.push(to+n),used[to+n]=true;
                if(used1[a[to].f]||used1[a[to].s])q1.push(to+n),used1[to+n]=true;
            }
        }
    }
    for(int i=0;i<m;i++){
        if(s[i]=='1')
        used1[i+1+n]=true;
        q1.push(i+1+n);
    }
    while(!q1.empty()){
        int v=q1.front();
        q1.pop();
        for(int to:g[v]){
            if(!used1[to])q1.push(to),used1[to]=true;
        }
    }
    for(int i=0;i<m;i++){
        if(used[i+n+1])cout<<'0';
        if(used1[i+n+1])cout<<'1';
        if(!used[i+n+1]&&!used1[i+n+1])cout<<'?';
    }
}

int main(){
    solve();
}

Compilation message

ili.cpp: In function 'int conv(std::string)':
ili.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=1;i<x.size();i++){
      |                 ~^~~~~~~~~

Subtask #1

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	31 ms	47300 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	31 ms	47300 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	31 ms	47300 KB	Output isn't correct
2	Halted	0 ms	0 KB	-