Submission #81861

#	Time	Username	Problem	Language	Result	Execution time	Memory
81861		Shtef	Zamjena (COCI18_zamjena)	C++14	70 / 70	195 ms	19172 KiB

zamjena

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14