oj.uz

Submission #89826

# Submission time Handle Problem Language Result Execution time Memory
89826 2018-12-18T14:00:20 Z tpoppo Zamjena (COCI18_zamjena) C++14
70 / 70
 566 ms 13664 KB 
#include <bits/stdc++.h>

using namespace std;
using ll= long long;

void NE(){
    cout<<"NE";
    exit(0);
}

void DA(){
    cout<<"DA";
    exit(0);
}

vector<string> a,b;
map<string,string> parent;
map<string,int> value;

string find(string a){
    if(parent[a] == a) return a;
    return parent[a] = find(parent[a]);
}

void merge(string a,string b){
    a = find(a);
    b = find(b);
    
    if(value[a] == -1e9 || value[b] == -1e9 || value[a] == value[b]){
        parent[b] = a;
        value[a] = max(value[a],value[b]);
    }else{
        NE();
    }
}


int main() {
    ll n;
    ll sn = 0;
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    a.resize(n);
    b.resize(n);
    for(auto&el:a){
        cin>>el;
        if(!isdigit(el[0])){
            value[el] = -1e9;
            parent[el] = el;
        }
    }

    for(auto&el:b){
        cin>>el;
        if(!isdigit(el[0])){
            value[el] = -1e9;
            parent[el] = el;        
        }
    }

    for(int i=0;i<n;i++){

        if(isdigit(a[i][0]) && isdigit(b[i][0])){
            if(a[i] != b[i]){
                NE();
            }
        }else if(isdigit(a[i][0]) || isdigit(b[i][0])){
            if(isdigit(a[i][0])) swap(a[i],b[i]);

            int c = stoi(b[i]);
            a[i] = find(a[i]);

            if(value[a[i]] != c && value[a[i]] != -1e9){
                NE();
            }
            value[a[i]] = c;
        }else{
            merge(a[i],b[i]);
        }
    }

    DA();
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:40:8: warning: unused variable 'sn' [-Wunused-variable]
     ll sn = 0;
        ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 528 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 756 KB Output is correct
2 Correct 5 ms 756 KB Output is correct
3 Correct 10 ms 1140 KB Output is correct
4 Correct 16 ms 1452 KB Output is correct
5 Correct 13 ms 1452 KB Output is correct
6 Correct 10 ms 1452 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2416 KB Output is correct
2 Correct 107 ms 4592 KB Output is correct
3 Correct 192 ms 7708 KB Output is correct
4 Correct 178 ms 8840 KB Output is correct
5 Correct 566 ms 13664 KB Output is correct
6 Correct 349 ms 13664 KB Output is correct