oj.uz

Submission #81861

# Submission time Handle Problem Language Result Execution time Memory
81861 2018-10-27T12:06:42 Z Shtef Zamjena (COCI18_zamjena) C++14
70 / 70
 195 ms 19172 KB 
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>
#include <map>
 
using namespace std;
 
typedef pair <string, int> psi;
#define x first
#define y second
#define mp make_pair
 
int n, c[50005], d[50005];
vector <string> r;
string a[50005], b[50005], vr[100005];
vector <int> ms[100005];
map <string, string> m;
 
bool dfs(int x, string s){
    if(vr[x].size()){
        if(vr[x] != s){
            return 0;
        }
        return 1;
    }
    vr[x] = s;
    bool ret = 1;
    for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
        int o = *i;
        ret = min(ret, dfs(o, s));
    }
    return ret;
}
 
bool isnumber(char c){
    return (c >= '0' && c <= '9');
}
 
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 0 ; i < n ; ++i){
    cin >> a[i];
    if(!isnumber(a[i][0]))
        r.push_back(a[i]);
}
for(int i = 0 ; i < n ; ++i){
    cin >> b[i];
    if(!isnumber(b[i][0]))
        r.push_back(b[i]);
}
sort(r.begin(), r.end());
r.resize(unique(r.begin(), r.end()) - r.begin());
for(int i = 0 ; i < n ; ++i){
    c[i] = lower_bound(r.begin(), r.end(), a[i]) - r.begin();
    d[i] = lower_bound(r.begin(), r.end(), b[i]) - r.begin();
}
for(int i = 0 ; i < n ; ++i){
    if(isnumber(a[i][0]) && isnumber(b[i][0])){
        if(a[i] != b[i]){
            cout << "NE" << endl;
            return 0;
        }
        continue;
    }
    if(!isnumber(a[i][0]) && !isnumber(b[i][0])){
        ms[c[i]].push_back(d[i]);
        ms[d[i]].push_back(c[i]);
        continue;
    }
    if(isnumber(a[i][0])){
        if(!((int)m[b[i]].size())){
            m[b[i]] = a[i];
        }
        else{
            if(m[b[i]] != a[i]){
                cout << "NE" << endl;
                return 0;
            }
        }
    }
    else{
        if(!((int)m[a[i]].size())){
            m[a[i]] = b[i];
        }
        else{
            if(m[a[i]] != b[i]){
                cout << "NE" << endl;
                return 0;
            }
        }
    }
}
for(int i = 0 ; i < n ; ++i){
    if(isnumber(a[i][0]) && isnumber(b[i][0]))
        continue;
    if((int)m[a[i]].size()){
        if(!dfs(c[i], m[a[i]])){
            cout << "NE" << endl;
            return 0;
        }
    }
    if((int)m[b[i]].size()){
        if(!dfs(d[i], m[b[i]])){
            cout << "NE" << endl;
            return 0;
        }
    }
}
cout << "DA" << endl;
 
return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8952 KB Output is correct
2 Correct 9 ms 9028 KB Output is correct
3 Correct 14 ms 9028 KB Output is correct
4 Correct 9 ms 9056 KB Output is correct
5 Correct 9 ms 9136 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9136 KB Output is correct
2 Correct 9 ms 9164 KB Output is correct
3 Correct 9 ms 9184 KB Output is correct
4 Correct 9 ms 9184 KB Output is correct
5 Correct 9 ms 9184 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9340 KB Output is correct
2 Correct 12 ms 9340 KB Output is correct
3 Correct 15 ms 9592 KB Output is correct
4 Correct 15 ms 9596 KB Output is correct
5 Correct 17 ms 9724 KB Output is correct
6 Correct 15 ms 9724 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10408 KB Output is correct
2 Correct 64 ms 12528 KB Output is correct
3 Correct 87 ms 14092 KB Output is correct
4 Correct 97 ms 14092 KB Output is correct
5 Correct 195 ms 19172 KB Output is correct
6 Correct 146 ms 19172 KB Output is correct