oj.uz

Submission #390179

# Submission time Handle Problem Language Result Execution time Memory
390179 2021-04-15T14:07:28 Z ioi Zamjena (COCI18_zamjena) C++14
70 / 70
 373 ms 20156 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 50001;

vector<string> g[N];
map<string , int > l;
map<string , int > mp ;
bool vis[N];
int nm ;
bool ntok = false;
map<int , string> aks ;

void dfs(int node){
    //cout << node << " " << nm << endl;
    vis[node] = true ;
    if(mp[aks[node]] && mp[aks[node]] != nm)ntok = true ;
    if(ntok)return ;


    for(auto &it : g[node]){
        if(vis[l[it]] == false){

            dfs(l[it]);
        }
        if(ntok)return ;
    }

}
int main()
{
    int n ;
    cin >> n ;
    int idx = 0 ;

    string a[n] , a2[n];

    for(int i = 0 ; i < n ; i ++)cin >> a[i];

    for(int i = 0 ; i < n ; i ++)cin >> a2[i];


    vector<pair<string , string> > e ;


    for(int i = 0 ; i < n ; i ++){
        char c = a[i][0] , c2 = a2[i][0];

        if(c < 97){
            if(c2 < 97){
                if(c != c2){
                    cout << "NE";
                    return 0 ;

                }
            }
            else {
                if(mp.count(a2[i]) && mp[a2[i]] != stoi(a[i])){
                    cout << "NE";
                    return 0;
                }
                else{

                 mp[a2[i]] = stoi(a[i]) ;
                 if(!l.count(a2[i]))l[a2[i]] = idx ++;

                   aks[l[a2[i]]] = a2[i];
                }
            }
        }
        else {
            if(c2 < 97){
                if(mp.count(a[i]) && mp[a[i]] != stoi(a2[i])){
                    cout << "NE";
                    return 0;
                }
                else {
                    mp[a[i]] = stoi(a2[i]) ;
                    if(!l.count(a[i]))l[a[i]] = idx ++ ;

                    aks[l[a[i]]] = a[i];
                }
            }
            else {
                if(!l.count(a[i]))l[a[i]] = idx ++ ;
                if(!l.count(a2[i]))l[a2[i]] = idx ++ ;
                aks[l[a[i]]] = a[i];
                aks[l[a2[i]]] = a2[i];

                g[l[a[i]]].push_back(a2[i]);
                g[l[a2[i]]].push_back(a[i]);


            }
        }
    }
   // cout << mp[aks[1]] << "\n\n\n";
    for(int i = 0 ; i < idx; i ++){
        if(!vis[i] && mp[aks[i]])
            nm = mp[aks[i]] , dfs(i);
            if(ntok){
                cout << "NE";
                return 0;
            }
    }
    cout << "DA";
}

Compilation message

zamjena.cpp: In function 'int main()':
zamjena.cpp:100:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  100 |         if(!vis[i] && mp[aks[i]])
      |         ^~
zamjena.cpp:102:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  102 |             if(ntok){
      |             ^~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1740 KB Output is correct
2 Correct 3 ms 1740 KB Output is correct
3 Correct 9 ms 2196 KB Output is correct
4 Correct 11 ms 2380 KB Output is correct
5 Correct 15 ms 2380 KB Output is correct
6 Correct 10 ms 2252 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4008 KB Output is correct
2 Correct 87 ms 7432 KB Output is correct
3 Correct 134 ms 10892 KB Output is correct
4 Correct 155 ms 12096 KB Output is correct
5 Correct 373 ms 20156 KB Output is correct
6 Correct 228 ms 14020 KB Output is correct