oj.uz

Submission #472621

# Submission time Handle Problem Language Result Execution time Memory
472621 2021-09-13T20:57:33 Z MamdouhN Zamjena (COCI18_zamjena) C++17
70 / 70
 103 ms 12796 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
 
 
 
 
vector<int> a;
vector<int> b;
 
bool isNumeric(string s){
    for(int i=0;i<s.size();i++){
        if(s[i]<'0'||s[i]>'9')return false;
    }
    return true;
}
 
int dsu[1000000];
 
 
int findIt(int x){
    if(x==dsu[x])return x;
    return dsu[x] = findIt(dsu[x]);
}
 
void unionIt(int x,int y){
    dsu[findIt(x)] = findIt(y);
}
 
 
map<string,int> variableMapper;
 
main()
{
    for(int i=0;i<1000000;i++)dsu[i]=i;
    int n;
    cin>>n;
 
    int cnt = 1;
 
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(isNumeric(s))a.push_back(stoi(s));
        else{
            if(variableMapper[s]==0){
                variableMapper[s] = 1000+cnt;
                cnt++;
            }
            a.push_back(variableMapper[s]);
        }
    }
 
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(isNumeric(s))b.push_back(stoi(s));
        else{
            if(variableMapper[s]==0){
                variableMapper[s] = 1000+cnt;
                cnt++;
            }
            b.push_back(variableMapper[s]);
        }
    }
 
    bool failure = false;
 
    for(int i=0;i<n;i++){
        if(failure)break;
        if(a[i]<=1000&&b[i]<=1000){
            if(a[i]!=b[i])failure = true;
            continue;
        }
        if(a[i]>1000&&b[i]<=1000){
            if(findIt(a[i])<=1000 && findIt(a[i])!= b[i]) failure = true;
            unionIt(a[i],b[i]);
            continue;
        }
        if(a[i]<=1000&&b[i]>1000){
            if(findIt(b[i])<=1000 && findIt(b[i])!= a[i]) failure = true;
            unionIt(b[i],a[i]);
            continue;
        }
        if(findIt(a[i])<=1000 && findIt(b[i])<=1000 && findIt(a[i])!=findIt(b[i]) ){
            failure = true;
            continue;
        }
        if(findIt(b[i])<=1000){
            unionIt(a[i],b[i]);
            continue;
        }
        unionIt(b[i],a[i]);
    }
 
    if(failure)cout<<"NE"<<endl;
    else cout<<"DA"<<endl;
}

Compilation message

zamjena.cpp: In function 'bool isNumeric(std::string)':
zamjena.cpp:12:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
zamjena.cpp: At global scope:
zamjena.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 4 ms 8012 KB Output is correct
3 Correct 4 ms 8012 KB Output is correct
4 Correct 4 ms 8012 KB Output is correct
5 Correct 4 ms 8012 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 4 ms 8012 KB Output is correct
3 Correct 5 ms 8012 KB Output is correct
4 Correct 4 ms 8012 KB Output is correct
5 Correct 5 ms 8012 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 4 ms 8012 KB Output is correct
3 Correct 4 ms 8012 KB Output is correct
4 Correct 4 ms 8012 KB Output is correct
5 Correct 4 ms 8088 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 5 ms 8168 KB Output is correct
3 Correct 8 ms 8356 KB Output is correct
4 Correct 8 ms 8404 KB Output is correct
5 Correct 8 ms 8376 KB Output is correct
6 Correct 8 ms 8268 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8712 KB Output is correct
2 Correct 40 ms 9704 KB Output is correct
3 Correct 55 ms 10684 KB Output is correct
4 Correct 68 ms 11284 KB Output is correct
5 Correct 103 ms 12796 KB Output is correct
6 Correct 81 ms 11036 KB Output is correct