oj.uz

Submission #715963

# Submission time Handle Problem Language Result Execution time Memory
715963 2023-03-28T15:36:53 Z Ahmed57 Ili (COI17_ili) C++14
100 / 100
 436 ms 5764 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 j = n+1;j<=n+m;j++){
        if(ze[adj[j][0]]&&ze[adj[j][1]])ze[j] = 1;
    }
    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]-'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
7.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 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4996 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct

Subtask #2
42.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 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4996 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 4 ms 4996 KB Output is correct
10 Correct 3 ms 5004 KB Output is correct
11 Correct 4 ms 5000 KB Output is correct
12 Correct 3 ms 5004 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct

Subtask #3
51.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 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4996 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 4 ms 4996 KB Output is correct
10 Correct 3 ms 5004 KB Output is correct
11 Correct 4 ms 5000 KB Output is correct
12 Correct 3 ms 5004 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 20 ms 5272 KB Output is correct
16 Correct 145 ms 5332 KB Output is correct
17 Correct 107 ms 5512 KB Output is correct
18 Correct 265 ms 5508 KB Output is correct
19 Correct 105 ms 5432 KB Output is correct
20 Correct 390 ms 5688 KB Output is correct
21 Correct 388 ms 5652 KB Output is correct
22 Correct 407 ms 5628 KB Output is correct
23 Correct 422 ms 5764 KB Output is correct
24 Correct 436 ms 5648 KB Output is correct
25 Correct 133 ms 5640 KB Output is correct
26 Correct 129 ms 5624 KB Output is correct
27 Correct 124 ms 5588 KB Output is correct
28 Correct 120 ms 5604 KB Output is correct
29 Correct 125 ms 5616 KB Output is correct
30 Correct 126 ms 5520 KB Output is correct
31 Correct 298 ms 5588 KB Output is correct
32 Correct 430 ms 5616 KB Output is correct