Submission #82828

#	Time	Username	Problem	Language	Result	Execution time	Memory
82828		heon	Zamjena (COCI18_zamjena)	C++11	70 / 70	220 ms	16356 KiB

zamjena

#include<bits/stdc++.h>
 
using namespace std;

map <string,int> bio;
map <string, vector <string>> graph;
 
bool check(char a){
    if(a >= 'A' && a <= 'z') return 1;
    else return 0;
}

void dfs(string a, int cnt){
    bio[a] = 1;
    if(!check(a[0])) cnt++;
    if(cnt >= 2){
        cout << "NE";
        exit(0);
    }
    for(auto x : graph[a]){
        if(bio.find(x) == bio.end()) dfs(x, cnt);
    }
}

 
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    string a[50005], b[50005];
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        cin >> b[i];
        if(check(b[i][0]) || check(a[i][0])){
            graph[b[i]].push_back(a[i]);
            graph[a[i]].push_back(b[i]);
        }
        if(!check(a[i][0]) && !check(b[i][0]) && a[i] != b[i]) return cout << "NE",0;
    }
 
    for(auto it = graph.begin(); it != graph.end(); it++){
        if(bio.find(it->first) == bio.end()){
            int cnt = 0;
            dfs(it->first, cnt);
        }
    }
    cout << "DA";
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14