oj.uz

Submission #82828

# Submission time Handle Problem Language Result Execution time Memory
82828 2018-11-01T22:56:15 Z heon Zamjena (COCI18_zamjena) C++11
70 / 70
 220 ms 16356 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3576 KB Output is correct
3 Correct 4 ms 3628 KB Output is correct
4 Correct 4 ms 3708 KB Output is correct
5 Correct 4 ms 3708 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3708 KB Output is correct
2 Correct 4 ms 3712 KB Output is correct
3 Correct 5 ms 3716 KB Output is correct
4 Correct 4 ms 3728 KB Output is correct
5 Correct 4 ms 3728 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4028 KB Output is correct
2 Correct 6 ms 4028 KB Output is correct
3 Correct 9 ms 4296 KB Output is correct
4 Correct 8 ms 4428 KB Output is correct
5 Correct 12 ms 4560 KB Output is correct
6 Correct 8 ms 4560 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5848 KB Output is correct
2 Correct 57 ms 8028 KB Output is correct
3 Correct 63 ms 9336 KB Output is correct
4 Correct 73 ms 10464 KB Output is correct
5 Correct 220 ms 16356 KB Output is correct
6 Correct 130 ms 16356 KB Output is correct